`REST` vs `SOAP` is _**not**_ the right question to ask.
 
`REST` is _**not**_ a web service communication protocol.

`REST` is an *architectural style* and a *design* for network-based software architectures.

`REST` and `SOAP` are _**not**_ mutually exclusive. A RESTful architecture may use `HTTP` or `SOAP` as the underlying communication protocol

@Abdulaziz's question does illuminate the fact that `REST` and `HTTP` are often used in tandem. This is primarily due to the simplicity of HTTP and its very natural mapping to RESTful principles.

**Fundamental REST Characteristics**

- **Resource**

 _Any concept that might be the target of a hypertext reference. Basically anything!_

- **Resource identifiers**

 _All resources are uniquely identified by resource identifiers e.g. uris_

- **Linked data**

 _Resources are linked using resource identifiers_

- **Stateless Communitcation**
 
 _Each request from client to server must contain all information necessary to understand the request. It must not take advantage of context on the server_
 
 _Actions are performed on a resource by using a representation to capture the current or intended state._

- **Representation**
 
 _A resource is represented as some sequence of bytes e.g. `XML`, `JSON`, `RDF`_

- **Uniform Interface**

 _Identification of resources manipulation of resources through representations, self-descriptive messages and, hypermedia as the engine of application state._

 _With `HTTP` `GET`, `PUT`, `POST`, `DELETE` create a very powerful, yet super simple uniform interface. Hence, the popularity of `REST` and `HTTP`_

 _Operations (depending on the op) carry special characteristics e.g. safe, idempotent, and/or cacheable_

See this blog [post][1] on **REST Design Principals** for more details on **REST** and the above stated bullets.

***EDIT:** corrected my comments on idempotent ops.*

 [1]: http://cdimascio.wordpress.com/2013/09/06/restful-design-principles/