Exhibit 5.01

[Cleary Gottlieb Steen & Hamilton LLP Letterhead]

July 12, 2011

Google Inc.

1600 Amphitheatre Parkway

Mountain View, CA 94043

Google Inc., a Delaware corporation (the “Company”), has created a Transferable Stock Option (“TSO”) program pursuant to which eligible employees of the Company may sell to participating financial institutions certain transferable, vested nonstatutory stock options that were granted to them under the Google Inc. 2004 Stock Plan (the “2004 Stock Plan”). A nonstatutory stock option sold by an employee to a participating financial institution pursuant to the TSO program will be deemed to be issued under the Warrant Agreement dated as of April 20, 2007 among the Company, the warrant agent and the warrantholders named therein, as amended by Amendment No. 1 thereto dated as of July 20, 2007 and by the Amendment Agreement dated as of July 12, 2011 among the Company, the auction manager, and the bidders named therein (the “Amendment Agreement”) (collectively, the “Warrant Agreement”) and will be automatically amended in accordance with the terms of the Warrant Agreement at the time of transfer (the resulting instrument, a “Warrant”). Such automatic amendments are described in the two forms of prospectus dated April 16, 2010, as supplemented by the prospectus supplements filed with the Securities and Exchange Commission (the “Commission”) pursuant to Rule 424(b) under the Securities Act of 1933, as amended (the “Securities Act”), on July 19, 2010 and July 12, 2011, respectively (collectively, the “Prospectuses”).

We have acted as counsel to the Company in connection with the offering pursuant to the registration statement on Form S-3 (File No. 333-166137) (the “Registration Statement”) and the two forms of prospectus filed with the Commission on July 12, 2011 pursuant to Rule 424(b) under the Securities Act (the “2011 Prospectuses”), of (i) up to an aggregate of 36,985,057 shares of the Company’s Class A common stock (the “Common Stock”), par value $0.001 per share, (x) issuable pursuant to the 2004 Stock Plan and (y) by participating financial institutions in connection with short sales of the Common Stock; and (ii) Warrants resulting from the sale pursuant to the TSO program of nonstatutory stock options currently outstanding or available for grant under the 2004 Stock Plan.

In arriving at the opinions expressed below, we have reviewed the following documents:

In addition, we have reviewed the originals or copies certified or otherwise identified to our satisfaction of such corporate records of the Company and such other documents, and we have made such investigations of law, as we have deemed appropriate as a basis for the opinions expressed below.

In rendering the opinions expressed below, we have assumed the authenticity of all documents submitted to us as originals and the conformity to the originals of all documents submitted to us as copies. In addition, we have assumed and have not verified the accuracy as to factual matters of each document that we have reviewed.

Based on the foregoing, and subject to the further assumptions and qualifications set forth below, it is our opinion that:

1. The shares of Common Stock issuable pursuant to the 2004 Stock Plan have been duly authorized by all necessary corporate action of the Company and, when issued in accordance with the terms of the 2004 Stock Plan, at prices not less than the par value thereof, will be validly issued, fully paid and nonassessable.

2. The shares of Common Stock to be offered by participating financial institutions in connection with short sales of Common Stock have been duly authorized by all necessary corporate action of the Company and are validly issued, fully paid and nonassessable.

2

3. When issued in accordance with the terms of the Warrant Agreement, the Warrants will be the valid, binding and enforceable obligations of the Company.

Insofar as the foregoing opinions relate to the validity, binding effect or enforceability of any agreement or obligation of the Company, (x) we have assumed that the Company and each other party to such agreement or obligation has satisfied those legal requirements that are applicable to it to the extent necessary to make such agreement or obligation enforceable against it (except that no such assumption is made as to the Company regarding matters of the law of the State of New York or the General Corporation Law of the State of Delaware that in our experience normally would be applicable to general business entities with respect to such agreement or obligation) and (y) such opinions are subject to applicable bankruptcy, insolvency or similar laws affecting creditors’ rights generally and to general principles of equity.

The foregoing opinions are limited to the law of the State of New York and the General Corporation Law of the State of Delaware (including the applicable provisions of the Delaware Constitution and the reported judicial decisions interpreting the General Corporation Law of the State of Delaware).

We hereby consent to the use of our name in the 2011 Prospectuses under the heading “Legal Matters,” as counsel for the Company who has passed on the validity of the Common Stock and the Warrants and to the use of this opinion as part of the Registration Statement (Exhibit 5.01). In giving such consent, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission thereunder. The opinions expressed herein are rendered on and as of the date hereof, and we assume no obligation to advise you or any other person, or to make any investigations, as to any legal developments or factual matters arising subsequent to the date hereof that might affect the opinions expressed herein.

3