Exhibit 5.1

[LETTERHEAD OF SHEPPARD, MULLIN, RICHTER & HAMPTON LLP]

July 11, 2008

Clean Energy Fuels Corp.
3020 Old Ranch Parkway, Suite 200
Seal Beach, CA 90740

Re:

Registration Statement on Form S-3

Ladies and Gentlemen:

        We have acted as counsel to Clean Energy Fuels Corp., a Delaware corporation (the "Company"), in connection with the filing by the Company of a registration statement on Form S-3 (the "Registration Statement") on the date hereof with the Securities and Exchange Commission (the "Commission") under the Securities Act of 1933, as amended (the "Securities Act"). The Registration Statement registers the following securities (collectively, the "Securities") to be offered and sold from time to time, on an immediate, continuous or delayed basis, pursuant to Rule 415 under the Securities Act having an aggregate offering price of up to $150,000,000:

        (i)    shares of common stock, par value $0.0001 per share, of the Company (the "Common Stock");

        (ii)   shares of preferred stock, par value $0.0001 per share, of the Company, in one or more series (the "Preferred Stock"), certain shares of which may be convertible into shares of Common Stock; and

        (iii)  warrants (the "Warrants") to purchase shares of Common Stock, shares of Preferred Stock or any combination of the foregoing.

The shares of Common Stock issued upon the sale of Common Stock or issuable upon the conversion of Preferred Stock or the exercise of Warrants are referred to herein collectively as the "Common Shares," and the shares of Preferred Stock issued upon the sale of Preferred Stock or issuable upon the exercise of Warrants are referred to herein collectively as the "Preferred Shares."

        This opinion is being furnished at your request in accordance with the requirements of Item 16 of Form S-3 and Item 601(b)(5)(i) of Regulation S-K promulgated by the Commission.

        Any Warrants are to be issued, either independently or together with other Securities, pursuant to one or more warrant agreements (each, a "Warrant Agreement") proposed to be entered into between the Company and a bank or trust company to be named therein, as warrant agent.

        In connection with this opinion, we have examined such matters of fact and questions of law as we have considered appropriate for purposes of rendering the opinions expressed below. In addition, we have been furnished with and have examined originals or copies of the Registration Statement, the Company's charter documents, the corporate proceedings taken by the Company with respect to the filing of the Registration Statement and the issuance of the Securities, and the originals or copies, certified or otherwise identified to our satisfaction, of such records, documents, certificates, memoranda and other instruments as we have considered necessary to provide a basis for the opinions hereinafter expressed. In such examination, we assumed (i) that the documents and instruments submitted to us have not been amended or modified since the date submitted, and (ii) the due execution and delivery of all documents where due execution and delivery are a prerequisite to the effectiveness thereof.

        Also, we have relied as to certain matters on information obtained from public officials, officers of the Company and other sources believed by us to be responsible, and we have assumed, without independent verification, that the parties to documents executed or to be executed, other than the Company, had or will have the capacity, if an individual, or the power, corporate or other, if an entity, to enter into and perform all obligations thereunder, the due authorization thereof by all requisite action, corporate or other, of such parties, and the due execution and delivery thereof by such parties,

and that the signatures on documents examined by us are genuine. In particular, we have assumed that all governing documents under which the Securities are to be issued will have been duly authorized, executed and delivered by all parties thereto other than the Company, and that any Warrants that may be issued pursuant to a Warrant Agreement will be manually signed or countersigned by duly authorized officers of the warrant agent thereunder.

        In addition, we have also assumed that at the time of the issuance and sale of the Securities, (i) the Registration Statement (including all necessary post-effective amendments thereto) will have become effective under the Securities Act; (ii) a prospectus supplement relating to and describing such Securities will have been duly prepared and filed with the Commission; and (iii) the terms of the Warrants, and of their issuance and sale, will have been duly established in conformity with the applicable Warrant Agreement and the resolutions of the board of directors (or a duly authorized committee thereof), of the Company, so as not to, and that the execution and delivery by the Company of, and the performance of its obligations under, the Warrant and the applicable Warrant Agreement, will not, violate, breach, conflict with or constitute a default under (A) the charter documents of the Company, or the resolutions of the board of directors (or the duly authorized committee thereof) of the Company relating to such transactions, (B) any agreement or instrument to which the Company or its properties is then subject, (C) any law, rule or regulation to which the Company or its properties is then subject, (D) any judicial or regulatory order or decree of any governmental authority having jurisdiction over the Company or its properties, or (E) any consent, approval, license, authorization or validation of, or filing, recording or registration with, any such governmental authority. We also have assumed that the Company is and, at the time of any such issuance and sale of Securities, will continue to be, duly organized, validly existing and in good standing under the laws of the State of Delaware.

        We have also assumed that (i) the stock certificates to be issued to represent the Common Shares or Preferred Shares, if certificated, will conform to the specimen Common Stock certificate or Preferred Stock certificates, as the case may be, submitted to us, (ii) shares of Common Stock and shares of Preferred Stock currently reserved by the Company will remain available for the issuance of the Common Shares or Preferred Shares, as the case may be, and (iii) none of the Company's charter documents, or the corporate proceedings taken by the Company with respect to the filing of the Registration Statement and the issuance of the Securities, will be rescinded, amended or otherwise modified prior to the issuance of the Securities, and there will not have occurred any change in law affecting the validity, legally binding character or enforceability thereof. We have obtained from officers of the Company a certificate as to certain factual matters and, insofar as this opinion is based on matters of fact, we have relied on such certificate without independent investigation.

        Based upon and subject to the foregoing and the qualifications and limitations set forth below, it is our opinion that:

        1.     When the terms of the Common Shares and of their issuance and sale have been duly established by the board of directors (or a duly authorized committee thereof) of the Company in conformity with the Company's certificate of incorporation and bylaws (and, in the case of adoption by a committee, the resolutions of the board delegating authority to such committee); when such Common Shares have been duly issued and sold as contemplated by the Registration Statement; if the number of Common Shares to be issued does not exceed the maximum authorized number of shares of Common Stock under the Company's certificate of incorporation, less any shares of Common Stock that may have been issued and are outstanding, or are reserved for issuance for other purposes, at such time; if such Common Shares are issued in certificated form, when the stock certificates to be issued to represent such Common Shares have been properly executed by the Company and countersigned by its transfer agent and registrar therefor in accordance with Section 158 of the Delaware General Corporation Law and the Company's bylaws and registered in the name of and duly delivered to, or if such Common Shares are issued in uncertificated form, such Common Shares have been properly registered by the Company or its

2

transfer agent in the name of, in either case the purchasers thereof upon payment of the agreed upon consideration therefor, which consideration has a value of not less than the par value per Common Share, in accordance with any duly authorized, executed and delivered underwriting, purchase, agency or similar agreement; and if all the foregoing actions are taken pursuant to authority granted in resolutions duly adopted by the board of directors (or a duly authorized committee thereof) of the Company, which resolutions specify the price or a proper pricing mechanism per share; and if, in the case of Common Shares issuable upon the conversion or exercise of other Securities, the Warrants which are exercisable for such Common Shares have been duly authorized, executed and delivered or the Preferred Shares which are convertible into such Common Shares have been duly authorized and validly issued and are fully paid and non-assessable, as the case may be; the Common Shares will be validly issued, fully paid and non-assessable.

        2.     When the terms of the Preferred Shares and of their issuance and sale have been duly established by the board of directors (or a duly authorized committee thereof) of the Company in conformity with the Company's certificate of incorporation and bylaws (and, in the case of adoption by a committee, the resolutions of the board delegating authority to such committee), whether in certificated or uncertificated form, including the adoption and filing with the Secretary of State of the State of Delaware of a Certificate of Designation for the series of Preferred Stock in accordance with the applicable provisions of the Company's certificate of incorporation and bylaws and the corporate laws of the State of Delaware (the "Certificate of Designation"); when such Preferred Shares have been duly issued and sold as contemplated by the Registration Statement; if the number of Preferred Shares to be issued does not exceed the maximum authorized number of shares of Preferred Stock under the Company's certificate of incorporation or the maximum number of shares of Preferred Stock of the applicable series set forth in the Certificate of Designations, less any shares of Preferred Stock or shares of Preferred Stock of such series, as the case may be, that may have been issued and are outstanding, or are reserved for issuance for other purposes, at such time; if such Preferred Shares are issued in certificated form, when the stock certificates to be issued to represent such Preferred Shares have been properly executed by the Company and, if applicable, countersigned by its transfer agent and registrar therefor in accordance with Section 158 of the Delaware General Corporation Law and the Company's bylaws, and registered in the name of and duly delivered to, or if such Preferred Shares are issued in uncertificated form, such Preferred Shares have been properly registered by the Company or its transfer agent in the name of, the purchasers thereof upon payment of the agreed upon consideration therefor, which consideration has a value of not less than the par value per Preferred Share, in accordance with any duly authorized, executed and delivered underwriting, purchase, agency or similar agreement; and if all the foregoing actions are taken pursuant to authority granted in resolutions duly adopted by the board of directors (or a duly authorized committee thereof) of the Company, which resolutions specify the price or a proper pricing mechanism per share; and if, in the case of Preferred Shares issuable upon the exercise of Warrants, such Warrants have been duly authorized, executed and delivered; the Preferred Shares will be validly issued, fully paid and non-assessable.

        3.     When a Warrant Agreement relating to the Warrants being offered by the Company has been duly authorized, executed and delivered by each party thereto and constitutes a valid, binding and enforceable agreement of each such party; when the terms of such Warrants have been duly established in conformity with such Warrant Agreement and the resolutions of the board of directors (or a duly authorized committee thereof) of the Company; when such Warrants have been duly executed and countersigned or authenticated in accordance with such Warrant Agreement and any resolutions of the board of directors (or a duly authorized committee thereof) or officers' certificate of the Company to be delivered or adopted in connection with the issuance of such Warrants; when such Warrants have been issued and sold as contemplated in the

3

Registration Statement and registered in the name of and duly delivered to the purchasers thereof upon payment of the agreed upon consideration therefor in accordance with such Warrant Agreement and any duly authorized, executed and delivered underwriting, purchase, agency or similar agreement; and if all the foregoing actions are taken pursuant to authority granted in resolutions duly adopted by the board of directors (or a duly authorized committee thereof) of the Company, such Warrants will constitute valid and legally binding obligations of the Company.

        The opinion set forth in paragraph 3 is qualified to the extent that the enforceability of any agreement, instrument or Security may be limited by or subject to (i) bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws of general applicability relating to or affecting creditors' rights and to general equity principles, (ii) public policy considerations which may limit the rights of parties to obtain remedies, and (iii) the implied covenants of good faith and fair dealing. We express no opinions concerning (i) the validity or enforceability of any provision contained in any Warrant Agreement that purports to waive or not give effect to rights to notices, defenses, subrogation or other rights or benefits that cannot be effectively waived under applicable law, or (ii) the enforceability of any indemnification provisions to the extent they purport to relate to liabilities resulting from or based upon negligence or any violation of federal or state securities laws.

        The foregoing opinions are limited to the Federal laws of the United States, the laws of the State of California, and the General Corporation Law of the State of Delaware, the applicable provisions of the Constitution of the State of Delaware, and reported decisions of the Delaware courts interpreting such laws and Constitution, and we are expressing no opinion as to the effect of the laws of any other jurisdiction.

        This opinion letter is rendered as of the date first written above and we disclaim any obligation to advise you of facts, circumstances, events or developments which hereafter may be brought to our attention and which may alter, affect or modify the opinion expressed herein. Our opinion is expressly limited to the matters set forth above and we render no opinion, whether by implication or otherwise, as to any other matters relating to the Registration Statement, any prospectuses contained therein or related thereto, the Company, any Securities, any Warrant Agreement, or any other instruments, agreements or transactions that may be related thereto or contemplated thereby. We are expressing no opinion as to any obligations that parties other than the Company may have under or in respect of the Warrants or Warrant Agreements, or as to the effect that their performance of such obligations may have upon any of the matters referred to above.

        We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference to our firm under the caption "Legal Matters" in the prospectus contained therein. In giving such consent, we do not thereby admit that we come within the category of persons whose consent is required under Section 7 of the Securities Act.

Very truly yours,

/s/ Sheppard, Mullin, Richter & Hampton LLP

4

QuickLinks

Exhibit 5.1