EXHIBIT 5.01

[Cleary Gottlieb Steen & Hamilton LLP Letterhead]

May 19, 2011

Google Inc.

1600 Amphitheatre Parkway

Mountain View, CA 94043

Ladies and Gentlemen:

We have acted as special United States counsel to Google Inc., a Delaware corporation (the “Company”), in connection with its offering pursuant to a registration statement on Form S-3 (No. 333-174228) (the “Registration Statement”) and the prospectus, dated May 16, 2011, as supplemented by the prospectus supplement thereto of even date therewith (together, the “Prospectus”), of $1,000,000,000 aggregate principal amount of 1.250% notes due 2014 (the “2014 Notes”), $1,000,000,000 aggregate principal amount of 2.125% notes due 2016 (the “2016 Notes”), and $1,000,000,000 aggregate principal amount of 3.625% notes due 2021 (together with the 2014 Notes and the 2016 Notes, the “Securities”). The Securities were issued pursuant to an indenture dated as of May 19, 2011 (the “Indenture”), between the Company and The Bank of New York Mellon Trust Company, N.A., as Trustee (the “Trustee”).

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

Google Inc., p. 2

In addition, we have reviewed the originals or copies certified or otherwise identified to our satisfaction of all 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 opinion expressed below.

In rendering the opinion 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 we have reviewed.

Based on the foregoing, and subject to the further assumptions and qualifications set forth below, it is our opinion that the Securities have been validly issued by the Company and are the valid, binding and enforceable obligations of the Company, entitled to the benefits of the Indenture.

Insofar as the foregoing opinion relates 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 federal law of the United States of America or 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 opinion is subject to applicable bankruptcy, insolvency and similar laws affecting creditors’ rights generally and to general principles of equity.

The foregoing opinion is limited to the federal law of the United States of America, 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 reported judicial decisions interpreting the General Corporation Law of the State of Delaware).

We hereby consent to the use of our name in the Prospectus under the heading “Legal Matters,” as counsel for the Company who has passed on the validity of the Securities and to the filing of this opinion as Exhibit 5.01 to the Company’s Current Report on Form 8-K dated May 19, 2011. 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 of 1933, as amended, or the rules and regulations of the Securities and Exchange Commission thereunder.

Google Inc., p. 3