Exhibit 5.1

August 5, 2015

Clean Energy Fuels Corp.
4675 MacArthur Court, Suite 800
Newport Beach, California 92660

Re:    Registration Statement on Form S-3

Ladies and Gentlemen:

        At your request, we have examined the Registration Statement on Form S-3 (the "Registration Statement"), filed by Clean Energy Fuels Corp., a Delaware corporation (the "Company"), with the Securities and Exchange Commission (the "Commission") in connection with the registration pursuant to the Securities Act of 1933, as amended (the "Act"), of the Securities (as defined below).

        The Registration Statement relates to the proposed issuance and sale, from time to time, pursuant to Rule 415 under the Act, as set forth in the Registration Statement, the prospectus contained therein (the "Prospectus") and the supplements to the prospectus referred to therein (each a "Prospectus Supplement"), of up to an aggregate offering price of $500,000,000, or the equivalent thereof, of shares of the Company's common stock, $0.0001 par value per share (the "Common Stock"), shares of the Company's preferred stock, $0.0001 par value per share (the "Preferred Stock"), warrants to purchase any of the securities described above (the "Warrants"), the Company's senior and subordinated debt securities (the "Debt Securities"), and units of securities of the Company (the "Units") composed of any combination of Common Stock, Preferred Stock, Warrants and Debt Securities (the Common Stock, the Preferred Stock, the Debt Securities, the Warrants and the Units are collectively referred to herein as the "Securities").

        The Securities are to be sold from time to time as set forth in the Registration Statement, the Prospectus contained therein and the Prospectus Supplements. The Debt Securities are to be issued pursuant to a senior or subordinated debt securities indenture (the "Indenture"), a form of which has been filed as an exhibit to the Registration Statement and is to be entered into between the Company and a trustee to be named in a Prospectus Supplement to the Registration Statement. The Securities are to be sold pursuant to a purchase, underwriting or similar agreement in substantially the form to be filed under a Current Report on Form 8-K. The Debt Securities are to be issued in the forms set forth in the Indenture. The Indenture may be supplemented in connection with the issuance of each such series of Debt Securities, by a supplemental indenture or other appropriate action of the Company creating such series of Debt Securities.

        We have examined instruments, documents, certificates and records that we have deemed relevant and necessary for the basis of our opinions hereinafter expressed. In such examination, we have assumed: (i) the authenticity of original documents and the genuineness of all signatures; (ii) the conformity to the originals of all documents submitted to us as copies; (iii) the truth, accuracy and completeness of the information, representations and warranties contained in the instruments, documents, certificates and records we have reviewed; (iv) that the Registration Statement, and any amendments thereto (including post-effective amendments), will have become effective under the Act; (v) that a Prospectus Supplement will have been filed with the Commission describing the Securities offered thereby; (vi) that all Securities will be issued and sold in compliance with applicable U.S. federal and state securities laws and in the manner stated in the Registration Statement and the

applicable Prospectus Supplement; (vii) that a definitive purchase, underwriting or similar agreement with respect to any Securities offered will have been duly authorized and validly executed and delivered by the Company and the other parties thereto; (viii) that any Securities issuable upon conversion, exchange, redemption or exercise of any Securities being offered will be duly authorized, created and, if appropriate, reserved for issuance upon such conversion, exchange, redemption or exercise; (ix) with respect to shares of Common Stock or Preferred Stock offered, that there will be sufficient shares of Common Stock or Preferred Stock authorized under the Company's organizational documents that are not otherwise reserved for issuance; and (x) the legal capacity of all natural persons. As to any facts material to the opinions expressed herein that were not independently established or verified, we have relied upon oral or written statements and representations of officers and other representatives of the Company.

        Based on such examination, we are of the opinion that:

        1.     With respect to shares of Common Stock, when both: (a) the Board of Directors of the Company or a duly constituted and acting committee thereof (such Board of Directors or committee being hereinafter referred to as the "Board") has taken all necessary corporate action to approve the issuance and the terms of the offering of the shares of Common Stock and related matters; and (b) certificates representing the shares of Common Stock have been duly executed, countersigned, registered and delivered either (i) in accordance with the applicable definitive purchase, underwriting or similar agreement approved by the Board, or upon the exercise of Warrants to purchase Common Stock, upon payment of the consideration therefor (not less than the par value of the Common Stock) provided for therein or (ii) upon conversion or exercise of any other Security, in accordance with the terms of such Security or the instrument governing such Security providing for such conversion or exercise as approved by the Board, for the consideration approved by the Board, then the shares of Common Stock will be validly issued, fully paid and nonassessable;

        2.     With respect to any particular series of shares of Preferred Stock, when both: (a) the Board has taken all necessary corporate action to approve the issuance and terms of the shares of Preferred Stock, the terms of the offering thereof, and related matters, including the adoption of a certificate of designation (a "Certificate") relating to such Preferred Stock conforming to the Delaware General Corporation Law (the "DGCL") and the filing of the Certificate with the Secretary of State of the State of Delaware; and (b) certificates representing the shares of Preferred Stock have been duly executed, countersigned, registered and delivered either (i) in accordance with the applicable definitive purchase, underwriting or similar agreement approved by the Board, or upon the exercise of Warrants to purchase Preferred Stock, upon payment of the consideration therefor (not less than the par value of the Preferred Stock) provided for therein or (ii) upon conversion or exercise of such Security or the instrument governing such Security providing for such conversion or exercise as approved by the Board, for the consideration approved by the Board, then the shares of Preferred Stock will be validly issued, fully paid and nonassessable;

        3.     With respect to the Warrants, when both: (a) the Board has taken all necessary corporate action to approve the issuance and terms of the Warrants and related matters; and (b) the Warrants have been duly executed and delivered against payment therefor, pursuant to the applicable definitive purchase, underwriting, warrant or similar agreement duly authorized, executed and delivered by the Company and a warrant agent, and the certificates for the Warrants have been duly executed and delivered by the Company and such warrant agent, then the Warrants will be validly issued and will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms;

2

        4.     With respect to Debt Securities to be issued under the Indenture, when: (a) the Trustee is qualified to act as Trustee under the Indenture and the Company has filed respective Form T-1s for the Trustee with the Commission; (b) the Trustee has duly executed and delivered the Indenture; (c) the Indenture has been duly authorized and validly executed and delivered by the Company to the Trustee; (d) the Indenture has been duly qualified under the Trust Indenture Act of 1939, as amended; (e) the Board has taken all necessary corporate action to approve the issuance and terms of such Debt Securities, the terms of the offering thereof and related matters; and (f) such Debt Securities have been duly executed, authenticated, issued and delivered in accordance with the provisions of the Indenture and the applicable definitive purchase, underwriting or similar agreement approved by the Board, or upon the exercise of Warrants to purchase Debt Securities, upon payment of the consideration therefor provided for therein, such Debt Securities will be validly issued and will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms, and entitled to the benefits of the Indenture; and

        5.     With respect to the Units, when: (a) the applicable unit agreement, if any, with respect to the Units has been duly authorized, executed and delivered by the Company and the other parties thereto, (b) the terms of the Units and the related Securities and their issuance and sale thereof have been duly established in conformity with the applicable contracts, agreements or indentures that are a component of the Units (including authorization of the issuance of any Securities to be issued pursuant to such Units), (c) the Units have been authorized, offered and sold in accordance with the applicable unit agreement, if any, the Registration Statement, including the prospectus supplement thereto, and, if in an underwritten offering, a valid and binding purchase, underwriting or agency agreement, and (d) the Units have been duly executed and delivered by the Company to the purchasers thereof in the manner contemplated in the applicable unit agreements upon payment of the agreed-upon consideration therefor, the Units will be binding obligations of the Company.

        Our opinion that any document is legal, valid and binding is qualified as to:

        (a)   limitations imposed by bankruptcy, insolvency, reorganization, arrangement, fraudulent conveyance, moratorium or other laws relating to or affecting the rights of creditors generally;

        (b)   rights to indemnification and contribution, which may be limited by applicable law or equitable principles; and

        (c)   general principles of equity, including without limitation concepts of materiality, reasonableness, good faith and fair dealing, and the possible unavailability of specific performance or injunctive relief and limitation of rights of acceleration, regardless of whether such enforceability is considered in a proceeding in equity or at law.

        Attorneys at our Firm are admitted to the practice of law in the States of New York and California, and we express no opinion as to the laws of any other jurisdiction, other than the Federal laws of the United States of America, the State of New York as to the enforceability of the Debt Securities and the DGCL. We are not licensed to practice law in the State of Delaware and, accordingly, our opinions as to the DGCL are based solely on a review of the official statutes of the state of Delaware and the applicable provisions of the Delaware Constitution and the reported judicial decisions interpreting such statutes and provisions.

        We hereby consent to the filing of this opinion as an exhibit to the above-referenced Registration Statement and to the use of our name wherever it appears in the Registration Statement, the Prospectus, any Prospectus Supplement, and in any amendment or supplement thereto. In giving such consent, we do not believe that we are "experts" within the meaning of such term as used in the Act or

3

the rules and regulations of the Commission issued thereunder with respect to any part of the Registration Statement, including this opinion as an exhibit.

Sincerely,

/s/ Morrison & Foerster LLP

Morrison & Foerster LLP

4

QuickLinks

Exhibit 5.1