In a strictly lawful perspective, a contract is a legally binding written agreement between two or more parties.
Some contracts, though, fall under what's called the "statute of frauds" - that means they must be written to become contracts.
http://www.expertlaw.com/library/business/statute_of_frauds....
> A "statute of frauds" requires that certain contracts be in writing, and that they be signed by all parties to be bound by the contract.
Contracts under statute of frauds include land sales and transfers, guaranteeing another person's debts, and contracts that can't be completed in a year.
It can be hard to prove an oral contract, but if you can prove it has all the elements of a contract, it's a contract, legal, and enforceable at least under the standard United States common law.