Exhibit 5.1

September 18, 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, as amended by Pre-Effective Amendment No. 1 to Form S-3 (as amended, 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 on a delayed or continuing basis, pursuant to Rule 415 under the Act, as set forth in the Registration Statement and the prospectus contained therein (the "Prospectus") and as to be set forth in one or more supplements to the Prospectus (each a "Prospectus Supplement"), of up to an aggregate offering price of $500,000,000, or the equivalent thereof, in one or more series of the following securities of the Company: (i) shares of the Company's common stock, $0.0001 par value per share (the "Common Stock"); (ii) shares of the Company's preferred stock, $0.0001 par value per share (the "Preferred Stock"); (iii) the Company's senior and subordinated debt securities (the "Debt Securities"); (iv) warrants to purchase Common Stock, Preferred Stock, Debt Securities or any combination thereof (the "Warrants"); (v) subscription rights (the "Rights") to purchase Common Stock, Preferred Stock, Debt Securities or other securities of the Company; and (vi) units (the "Units") composed of any combination of Common Stock, Preferred Stock, Debt Securities and Warrants (the Common Stock, the Preferred Stock, the Debt Securities, the Warrants, the Rights and the Units are collectively referred to herein as the "Securities").

        The Securities are to be sold from time to time on a delayed or continuous basis as set forth in the Registration Statement, the Prospectus contained therein and one or more Prospectus Supplements. The Debt Securities are to be issued pursuant to a senior or subordinated debt securities indenture, a form of which has been filed as Exhibit 4.1 to the Registration Statement, as amended or supplemented from time to time (the "Indenture"), to be entered into between the Company and a trustee to be named in a Prospectus Supplement (the "Trustee").

        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 issuance, sale, amount and terms of any Securities to be offered from time to time under the Registration Statement will have been duly authorized and established by proper action of the Board of Directors of the Company or a duly authorized committee of the Board of Directors ("Board Action") in accordance with the Company's Articles of Incorporation and bylaws and applicable provisions of Delaware corporate law, in a manner

that does not violate any law, government or court-imposed order or restriction or agreement or instrument then binding on the Company or otherwise impair the valid or binding nature of the obligations represented by the applicable Securities; (v) that, at the time of offer, issuance and sale of any Securities, the Registration Statement, and any amendments thereto (including post-effective amendments), will have become effective under the Act and no stop order suspending its effectiveness will have been issued and remain in effect; (vi) that a Prospectus Supplement will have been filed with the Commission describing the Securities offered thereby; (vii) 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; (viii) that, prior to the issuance of any Securities, 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; (ix) that, if being sold by the Company, any Securities will be delivered against payment of valid consideration therefor and in accordance with the terms of the applicable Board Action authorizing such sale and any applicable purchase, underwriting or similar agreement with respect to such Securities and as contemplated by the Registration Statement and/or the applicable Prospectus Supplement; (x) that any Debt Securities will be issued under the Indenture; (xi) that any Warrants will be issued under one or more warrant agreements, each to be between the Company and a bank, trust company, or other financial institution identified therein as warrant agent; (xii) that any Rights will be issued under on or more rights agreements, each to be between the Company and a bank or trust company identified therein as rights agent; (xiii) that any Units will be issued under one or more unit agreements, each to be among the Company, one or more institutions identified therein as unit agent, and the holders thereof; (xiv) 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; (xv) 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; (xvi) with respect to shares of Preferred Stock, that a Certificate of Designation setting forth the number of shares and the terms of any class or series of Preferred Stock will be filed and accepted for record by the Secretary of State of the State of Delaware prior to their issuance; (xvii) that the terms of the Securities will conform in all material respects to the respective descriptions thereof in the Prospectus; (xviii) that certificates, if required, representing the Securities will be duly executed and delivered and, to the extent required by any applicable agreement, duly authenticated and countersigned; (xix) that the Company will remain a Delaware corporation; (xx) that the laws of the State of New York will be the governing law with respect to any warrant agreement, rights agreement or unit agreement; and (xxi) 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.

        To the extent that the obligations of the Company with respect to the Securities may be dependent upon such matters, we assume for purposes of this opinion that the other party or parties, as applicable, under the Indenture, under the warrant agreement for any Warrants, under the rights agreement for any Rights, and under the unit agreement, for any units, namely, the Trustee, the warrant agent, the rights agent, the unit agent, or the unit holder, respectively, is duly organized, validly existing and in good standing under the laws of its jurisdiction of organization; that such other party will be duly qualified to engage in the activities contemplated by the Indenture, such warrant agreement, rights agreement or unit agreement, as applicable; that the Indenture, such warrant agreement, rights agreement or unit agreement, as applicable, will have been duly authorized, executed and delivered by the other party and will constitute the legal, valid and binding obligation of the other party enforceable against the other party in accordance with its terms; that such other party will be in compliance with respect to performance of its obligations under the Indenture, such warrant agreement

2

or rights agreement, as applicable, with all applicable laws and regulations; that such other party will have the requisite organizational and legal power and authority to perform its obligations under the Indenture, such warrant agreement, rights agreement or unit agreement, as applicable; and that a Statement of Eligibility of the Trustee on Form T-1 has been properly filed with the Commission.

        Based upon, subject to and limited by the foregoing, we are of the opinion that:

        1.     With respect to any shares of Common Stock, upon completion of the Board Action, the Common Stock will be duly authorized and, when and if issued and delivered against payment therefor in accordance with the Registration Statement and the Board Action, will be validly issued, fully paid and nonassessable;

        2.     With respect to any particular series of shares of Preferred Stock, upon completion of the Board Action and the filing of the applicable Certificate of Designations with the Secretary of State of the State of Delaware, the Preferred Stock will be duly authorized and, when and if issued and delivered against payment therefor in accordance with the Registration Statement and the Board Action and the Certificate of Designations, will be validly issued, fully paid and nonassessable;

        3.     With respect to any Warrants, upon completion of the Board Action and the due execution and delivery of a warrant agreement relating thereto on behalf of the Company and the warrant agent named therein and due authentication of the Warrants by such warrant agent, and upon due execution and delivery of the Warrants on behalf of the Company, the Warrants will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms;

        4.     With respect to any Debt Securities, upon completion of the Board Action and the due execution and delivery of the Indenture on behalf of the Company and the Trustee, the Debt Securities will be duly authorized and, upon the due authentication by the Trustee and due execution and delivery on behalf of the Company in accordance with the Indenture, will constitute valid and binding obligations of the Company;

        5.     With respect to any Rights, upon completion of the Board Action and the due execution and delivery of a rights agreement relating to the Rights on behalf of the Company and the rights agent named therein, the Rights will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms; and

        6.     With respect to any Units, upon completion of the Board Action and the due execution and delivery of a unit agreement relating to the Units on behalf of the Company and the other parties thereto, the Units will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

        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

3

laws of the United States of America, the State of New York as to the enforceability of the Debt Securities and the Delaware General Corporation Law (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 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