Exhibit 5.1

December 21, 2016

Board of Directors

Clean Energy Fuels Corp.

4675 MacArthur Court, Suite 800

Newport Beach, CA 92660

Ladies and Gentlemen:

We are acting as counsel to Clean Energy Fuels Corp., a Delaware corporation (the “Company”), in connection with the issuance and sale by the Company from time to time of shares of its common stock, par value $0.0001 per share (the “Common Stock”), having an aggregate offering price of up to $200,000,000 (the “Shares”), pursuant to a prospectus supplement dated December 21, 2016 and the accompanying base prospectus dated November 3, 2015 (such documents, collectively, the “Prospectus”) that form part of the Company’s effective registration statement on Form S-3 (File No. 333-206121) (as amended, the “Registration Statement”), filed by the Company with the United States Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Securities Act”). The Shares are to be sold by the Company pursuant to the terms of the Second Amended and Restated Equity Distribution Agreement, dated December 21, 2016, by and between the Company and Citigroup Global Markets Inc. (the “Agreement”) and in the manner described in the Registration Statement and the Prospectus. The Shares will be issued from time to time in public offerings at market or negotiated prices under Rule 415 of the Securities Act.

As counsel for the Company, we have examined the Agreement, the Registration Statement, the Prospectus, the Company’s Restated Certificate of Incorporation, as amended (the “Certificate of Incorporation”), and the Company’s Amended and Restated Bylaws, as amended, as well as originals or copies, certified or otherwise identified to our satisfaction, of such other documents, corporate records, certificates of public officials and other instruments as we have deemed necessary for the purposes of rendering this opinion, and we are familiar with the proceedings taken and proposed to be taken by the Company in connection with the authorization, issuance and sale of the Shares. In our examination, we have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals and the conformity with the originals of all documents submitted to us as copies. We have further assumed that, upon the issuance of any of the Shares, the total number of shares of Common Stock issued and outstanding will not exceed the total number of shares of Common Stock that the Company is then authorized to issue under the Certificate of Incorporation. This opinion letter is given, and all statements herein are made, in the context of the foregoing.

This opinion letter is based as to matters of law solely on the General Corporation Law of the State of Delaware, as currently in effect. We express no opinion herein as to any other laws, statutes, ordinances, rules or regulations. As used herein, the term “General Corporation Law of the State of Delaware, as currently in effect” includes the statutory provisions contained therein, all applicable provisions of the Delaware Constitution and reported judicial decisions interpreting these laws.

Based upon, subject to and limited by the foregoing, it is our opinion that, upon issuance, delivery and payment therefor in the manner contemplated by the Registration Statement, the Prospectus, the Agreement and the resolutions of the Board of Directors or a duly authorized committee thereof, the Shares will be legally issued, fully paid and nonassessable.

This opinion is furnished to you in connection with the filing by the Company of a Current Report on Form 8-K relating to the offer and sale of the Shares, which Current Report on Form 8-K will be incorporated by reference into the Registration

December 21, 2016

Page Two

Statement and the Prospectus, and may not be relied upon for any other purpose without our express written consent. No opinion may be implied or inferred beyond the opinion expressly stated. This opinion is given as of the date hereof, and we assume no obligation to advise you of any changes in applicable law or any facts or circumstances that come to our attention after the date hereof that may affect the opinion contained herein.

We hereby consent to the filing of this opinion as an exhibit to the above-described Current Report on Form 8-K and to the reference to our firm contained under the heading “Legal Matters” in the Prospectus. In giving this consent, we do not admit that we are in the category of persons whose consent is required by Section 7 of the Securities Act or the rules and regulations promulgated by the Commission.

Very truly yours,

/s/ Morrison & Foerster LLP

Morrison & Foerster LLP