Exhibit 5.1

July 1, 2016

Gevo, Inc.

345 Inverness Drive South

Building C, Suite 310

Englewood, Colorado 80112

Re: Gevo, Inc. – Registration Statement on Form S-3

Ladies and Gentlemen:

We have acted as counsel to Gevo, Inc., a Delaware corporation (the “Company”), in connection with the registration statement on Form S-3 (the “Registration Statement”) to be filed with the Securities and Exchange Commission (the “Commission”) by the Company on the date hereof under the Securities Act of 1933, as amended (the “Act”), including the prospectus included therein (the “Prospectus”).

The Registration Statement relates to the issuance and sale by the Company from time to time, pursuant to Rule 415 of the rules and regulations promulgated under the Act, of an unspecified amount of securities of the Company up to an aggregate offering price of $130,000,000 and consisting of: (i) shares of the Company’s common stock, par value $0.01 per share (the “Common Stock”); (ii) shares of the Company’s preferred stock, par value $0.01 per share, to be issued in one or more series (the “Preferred Stock”); (iii) senior debt securities or subordinated debt securities (the “Debt Securities”) to be issued in one or more series under a form of senior indenture filed as Exhibit 4.4 to the Registration Statement or under a form of subordinated indenture filed as Exhibit 4.5 to the Registration Statement, as such indentures may be amended or supplemented from time to time (each an “Indenture” and collectively the “Indentures”) proposed to be entered into by and between the Company, as issuer, and a trustee to be named (the “Trustee”); (iv) warrants (the “Warrants”) to purchase Common Stock, Preferred Stock and/or Debt Securities, in one or more series, as shall be designated by the Company at the time of the offering; and (v) units (the “Units”) consisting of any of the Common Stock, Preferred Stock, Debt Securities and/or Warrants or any combination of such securities. The Common Stock, Preferred Stock, Debt Securities, Warrants and Units are collectively referred to herein as the “Offered Securities.” The Registration Statement also relates to the issuance of up to 15,076,495 shares of Common Stock (the “Warrant Shares”) upon the exercise of the Company’s outstanding warrants issued pursuant to that certain Common Stock Unit Warrant Agreement between the Company and American Stock Transfer & Trust Company, LLC (the “Warrant Agent”), dated December 16, 2013 (the “2013 Warrants”), the Company’s outstanding warrants issued pursuant to that certain Common Stock Unit Warrant Agreement between the Company and the Warrant Agent, dated August 5, 2014 (the “2014 Warrants”), the Company’s outstanding warrants issued pursuant to that certain 2015 Common Stock Unit Series A Warrant Agreement between the Company and the Warrant Agent, dated February 3, 2015 (the “Series A Warrants”), the Company’s outstanding warrants issued pursuant to that certain 2015 Common Stock Unit Series C Warrant Agreement between the Company and the Warrant Agent, dated May 19, 2015 (the “Series C Warrants”), the Company’s outstanding Series D Warrants to Purchase Common Stock, issued December 11, 2015 (the “Series D Warrants”), the Company’s outstanding Series F Warrants to Purchase Common Stock, issued April 1, 2016 (the “Series F Warrants”), and the Company’s outstanding Series H Warrants to Purchase Common Stock, issued April 1, 2016 (the “Series H Warrants” and, together with the 2013 Warrants, the 2014 Warrants, the Series A Warrants, the Series C Warrants, the Series D Warrants and the Series F Warrants, the “Outstanding Warrants”). The Registration Statement provides that the Offered Securities may be offered from time to time in amounts, at prices and on terms to be set forth in one or more supplements to the Prospectus (each, a “Prospectus Supplement”). This opinion is being delivered in accordance with the requirements of

July 1, 2016

Page 2

Item 601(b)(5) of Regulation S-K under the Act, and no opinion is expressed herein as to any matter pertaining to the contents of the Registration Statement, the Prospectus or any Prospectus Supplement, other than as expressly stated herein with respect to the issuance of the Offered Securities, the Outstanding Warrants or the Warrant Shares.

As such counsel and for purposes of our opinions set forth below, we have examined originals or copies, certified or otherwise identified to our satisfaction, of such documents, corporate records, certificates of public officials and other instruments as we have deemed necessary or appropriate as a basis for the opinions set forth herein, including, without limitation:

(i) the Registration Statement;

(ii) the Prospectus;

(iii) the form of the senior indenture;

(iv) the form of the subordinated debt indenture;

(v) the Common Stock Unit Warrant Agreement between the Company and the Warrant Agent, dated December 16, 2013;

(vi) the Common Stock Unit Warrant Agreement between the Company and the Warrant Agent, dated August 5, 2014;

(vii) the 2015 Common Stock Unit Series A Warrant Agreement between the Company and the Warrant Agent, dated February 3, 2015;

(viii) the 2015 Common Stock Unit Series C Warrant Agreement between the Company and the Warrant Agent, dated May 19, 2015;

(ix) the forms of Series D Warrant, Series F Warrant and Series H Warrant;

(x) the amended and restated certificate of incorporation of the Company, as amended, certified as of March 28, 2016 by the Secretary of State of the State of Delaware (the “Certificate of Incorporation”), and the amended and restated bylaws of the Company, certified by an officer of the Company as of the date hereof (the “Bylaws” and together with the Certificate of Incorporation, the “Charter Documents”);

(xi) a certificate of the Secretary of State of the State of Delaware as to the incorporation and good standing of the Company under the laws of the State of Delaware as of May 13, 2016;

(xii) a copy of the resolutions adopted by the Board of Directors of the Company (the “Board”) on May 13, 2016, certified by an officer of the Company as of the date hereof, relating to, among other things, the Registration Statement and the issuance by the Company of securities, up to an aggregate offering price of $150,000,000, consisting of: (a) Common Stock; (b) Preferred Stock; (c) Debt Securities; (d) Warrants; and (e) Units;

(xiii) copies of the resolutions adopted by the Board on November 15, 2013, July 24, 2014, January 16, 2015, May 13, 2015 and September 29, 2015, and by the Pricing Committee of the Board on December 11, 2013, July 30, 2014, January 28, 2015, May 13, 2015, December 7, 2015 and March 28, 2016, certified by an officer of the Company as of the date hereof, relating to, among other things, the issuance by the Company of the Outstanding Warrants and the Warrant Shares;

(xiv) certificates of officers and representatives of the Company.

In addition to the foregoing, we have made such investigations of law as we have deemed necessary or appropriate as a basis for the opinions and views set forth herein.

In such examination and in rendering the opinions expressed below, we have assumed: (i) the due authorization, execution and delivery of all documents by all the parties thereto; (ii) the genuineness of all signatures on all documents submitted to us; (iii) the authenticity and completeness of all documents,

July 1, 2016

Page 3

corporate records, certificates and other instruments submitted to us; (iv) that photocopy, electronic, certified, conformed, facsimile and other copies submitted to us of original documents, corporate records, certificates and other instruments conform to the original documents, records, certificates and other instruments, and that all such original documents, corporate records, certificates and other instruments were authentic and complete; (v) the legal capacity and competency of all individuals executing documents; (vi) that no documents submitted to us have been amended or terminated orally or in writing except as has been disclosed to us; (vii) that the statements contained in the certificates and comparable documents of public officials, officers and representatives of the Company and other persons on which we have relied for the purposes of this opinion letter are true and correct; (viii) that each of the officers and directors of the Company has properly exercised his or her fiduciary duties; (ix) that New York law will be chosen to govern the Debt Securities, the Indentures and any related supplemental indenture, the Warrants and any related warrant agreements, and the Units and any related unit agreements and that such choice is legally enforceable, and that the Debt Securities, Indentures, the Warrants and any related warrant agreements, and the Units and any related unit agreements will contain all provisions required under the laws of the State of Delaware in respect of contracts for the sale of securities issued by a Delaware corporation; (x) that there are no agreements or understandings between or among the parties to the Debt Securities, the Indentures, the Warrants, or the Units that would expand, modify or otherwise affect the terms of such agreements or instruments or the respective rights or obligations of the parties thereunder and (xii) that the Debt Securities, the Indentures, the Warrants, and the Units will conform to the descriptions thereof set forth in the Prospectus. As to all questions of fact material to this opinion letter, we have relied (without independent investigation) upon certificates or comparable documents of officers and representatives of the Company. Based upon the foregoing, and in reliance thereon, and subject to the limitations, qualifications and exceptions set forth herein, we are of the following opinion:

1. With respect to any shares of Common Stock to be offered by the Company pursuant to the Registration Statement (including the Warrant Shares and any shares of Common Stock to be issued upon the exchange, exercise or conversion of Offered Securities that are exchangeable or exercisable for, or convertible into, Common Stock), when (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act; (ii) a Prospectus Supplement with respect to such shares Common Stock has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder; (iii) if such shares of Common Stock are to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to such shares of Common Stock has been duly authorized, executed and delivered by the Company and the other parties thereto; (iv) the Board, including any appropriate committee thereof appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance and terms of such shares of Common Stock and related matters; and (v) such shares of Common Stock have been duly issued and delivered against payment of the consideration therefor (not less than the par value of the Common Stock) as contemplated by the Registration Statement, Prospectus, any applicable Prospectus Supplement and any applicable agreements or corporate actions relating thereto, such shares of Common Stock will be validly issued, fully paid and nonassessable.

2. With respect to any shares of Preferred Stock to be offered by the Company pursuant to the Registration Statement (including any shares of Preferred Stock to be issued upon the exchange, exercise or conversion of Offered Securities that are exchangeable or exercisable for, or convertible into, Preferred Stock), when (i) a series of Preferred Stock has been duly established in accordance with the terms of the Certificate of Incorporation and applicable law and authorized by all necessary corporate action of the Company; (ii) the relative rights, preferences, qualifications and limitations of such series of Preferred Stock have been designated by all necessary corporate action of the Company and set forth in a Certificate of Designations properly filed with the Secretary of State of the State of Delaware; (iii) the

July 1, 2016

Page 4

Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act; (iv) a Prospectus Supplement with respect to such shares Preferred Stock has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder; (v) if such shares of Preferred Stock are to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to such shares of Preferred Stock has been duly authorized, executed and delivered by the Company and the other parties thereto; (vi) the Board, including any appropriate committee thereof appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance and terms of such shares of Preferred Stock and related matters; and (vii) such shares of Preferred Stock have been duly issued and delivered against payment of the consideration therefor (not less than the par value of the Preferred Stock) as contemplated by the Registration Statement, Prospectus, any applicable Prospectus Supplement and any applicable agreements or corporate actions relating thereto, such shares of Preferred Stock will be validly issued, fully paid and nonassessable.

3. With respect to any series of Debt Securities to be offered by the Company pursuant to the Registration Statement, including any Debt Securities to be issued upon the exchange, exercise or conversion of Offered Securities that are exchangeable or exercisable for, or convertible into, Debt Securities (the “Offered Debt Securities”), when (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act and the Indentures and any supplemental indentures have been qualified under the Trust Indenture Act; (ii) a Prospectus Supplement with respect to the Offered Debt Securities has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder; (iii) if the Offered Debt Securities are to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to the Offered Debt Securities has been duly authorized, executed and delivered by the Company and the other parties thereto; (iv) the Board, including any appropriate committee thereof appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance and terms of the Offered Debt Securities and related matters; (v) the Indentures and any supplemental indenture to be entered into in connection with the issuance of the Offered Debt Securities have been duly authorized, executed and delivered by each party thereto; (vi) the terms of the Offered Debt Securities and of their issuance and sale have been duly established in conformity with the Indentures and any applicable supplemental indentures so as not to violate any applicable law or Charter Documents, or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company; and (vii) the Offered Debt Securities have been issued in a form that complies with the Indentures and have been duly executed and authenticated in accordance with the provisions of the Indentures and any applicable supplemental indenture to be entered into in connection with the issuance of the Offered Debt Securities and duly delivered to the purchasers thereof upon payment of the agreed-upon consideration therefor in the manner contemplated in the Registration Statement or any Prospectus Supplement relating thereto, the Offered Debt Securities, when issued and sold in accordance with the Indentures and any applicable supplemental indenture to be entered into in connection with the issuance of the Debt Securities and the applicable underwriting agreement, if any, or any other duly authorized, executed and delivered valid and binding purchase or agency agreement, will constitute the valid and binding obligations of the Company, enforceable against the Company in accordance with their respective terms.

4. With respect to any series of Warrants to be offered by the Company pursuant to the Registration Statement (the “Offered Warrants”), when (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act and any Indentures and supplemental indentures to be entered into in connection with the issuance of any Debt Securities related to such Offered Warrants have been qualified under the Trust Indenture Act; (ii) a

July 1, 2016

Page 5

Prospectus Supplement with respect to the Offered Warrants and any Offered Securities issuable upon the exercise of the Offered Warrants has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder; (iii) if the Offered Warrants are to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to the Offered Warrants has been duly authorized, executed and delivered by the Company and the other parties thereto; (iv) the Board, including any appropriate committee thereof appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance and terms of the Offered Warrants and related matters; (v) the warrant agreement, if any, to be entered into in connection with the issuance of the Offered Warrants and any Indentures and supplemental indentures to be entered into in connection with the issuance of any Debt Securities relating to such Offered Warrants have been duly authorized, executed and delivered by each party thereto; (vi) the terms of the Offered Warrants and any Debt Securities related to such Offered Warrants have been duly established in conformity with the applicable warrant agreement, if any, the Indentures and supplemental indentures governing any Debt Securities relating to such Offered Warrants, and applicable law and authorized by all necessary corporate action of the Company so as not to violate any applicable law or the Charter Documents or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company; (vii) the Common Stock or the Preferred Stock issuable upon exercise of the Offered Warrants have been duly authorized and reserved for issuance; (viii) the Debt Securities issuable upon exercise of the Offered Warrants have been duly authorized, executed and authenticated in accordance with the provisions of the applicable Indenture and any applicable supplemental indenture thereto, and reserved for delivery to the purchasers thereof upon exercise of the Offered Warrants and payment of the agreed-upon consideration therefor; and (ix) the Offered Warrants have been duly executed, delivered, countersigned, issued and sold against payment therefor in accordance with the provisions of the applicable warrant agreement, if any, the Offered Warrants will constitute the valid and binding obligations of the Company, enforceable against the Company in accordance with their respective terms.

5. With respect to any series of Units to be offered by the Company pursuant to the Registration Statement (the “Offered Units”), when (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act and any Indentures and supplemental indentures to be entered into in connection with the issuance of any Debt Securities related to such Offered Units have been qualified under the Trust Indenture Act; (ii) a Prospectus Supplement with respect to the Offered Units and any Offered Securities included in, or issuable upon the exercise of, the Offered Units has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder; (iii) if the Offered Units are to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to the Offered Units has been duly authorized, executed and delivered by the Company and the other parties thereto; (iv) the Board, including any appropriate committee thereof appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance and terms of the Offered Units and related matters; (v) the unit agreement, if any, to be entered into in connection with the issuance of the Offered Units and any Indenture or supplemental indenture to be entered into in connection with the issuance of any Debt Securities related to such Offered Units have been duly authorized, executed and delivered by each party thereto; (vi) the terms of the Offered Units and any Debt Securities related to such Offered Units and their issuance and sale have been duly established in conformity with the applicable unit agreement, if any, and Indentures and supplemental indentures so as not to violate any applicable law or the Charter Documents or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company; (vii) any Common Stock or the Preferred Stock relating to the Offered Units have been duly authorized and reserved for issuance;

July 1, 2016

Page 6

(viii) any Debt Securities relating to the Offered Units have been duly executed and authenticated in accordance with the provisions of the Indentures and any applicable supplemental indenture thereto, and duly delivered to the purchasers thereof upon exercise of the Offered Units and payment of the agreed-upon consideration therefor; (ix) any Warrants relating to the Offered Units have been duly executed and authenticated in accordance with the provisions of the applicable warrant agreement, if any, and duly delivered to the purchasers thereof upon exercise of the Offered Units and payment of the agreed-upon consideration therefor; and (x) the Offered Units have been duly executed, delivered, countersigned, issued and sold in accordance with the provisions of the applicable unit agreement, if any, the Offered Units, when issued and sold in accordance with the applicable unit agreement, if any, and the applicable underwriting agreement, or any other duly authorized, executed and delivered valid and binding purchase or agency agreement, will constitute the valid and binding obligations of the Company, enforceable against the Company in accordance with their respective terms.

The opinions expressed herein are subject to the following exceptions, qualifications and limitations:

A. They are limited by the effect of (a) any applicable bankruptcy, insolvency, reorganization, moratorium or similar law and principles affecting creditors’ rights generally, including without limitation fraudulent transfer or fraudulent conveyance laws and (b) general principles of equity (including, without limitation, concepts of materiality, reasonableness, good faith and fair dealing) and the availability of equitable remedies (including, without limitation, specific performance and equitable relief), regardless of whether considered in a proceeding in equity or at law.

B. With reference to, but without limiting in any way, qualification (A) above: provisions regarding the recovery of attorneys’ fees for a person who is not the prevailing party in a final proceeding, provisions imposing a payment obligation with respect to the Company’s obligations and provisions whereby a party purports to ratify acts in advance of the occurrence of such acts, are or may be unenforceable in whole or in part under applicable law.

C. No opinion is expressed herein with respect to (i) the validity or enforceability of any provision of the Offered Securities that requires a person or entity to cause another person or entity to take or refrain from taking action under circumstances in which such person or entity does not control such other person or entity, (ii) the validity of enforceability of any provision of the Offered Securities insofar as it purports to effect a choice of governing law or choice of forum for the adjudication of disputes, and (iii) the acceptance by a Federal court located in the State of New York of jurisdiction in a dispute arising under the Offered Securities.

Without limiting any of the other limitations, exceptions and qualifications stated elsewhere herein, we express no opinion or view with regard to the applicability or effect of the law of any jurisdiction other than, as in effect on the date of this letter, the General Corporation Law of the State of Delaware and, with respect to our opinions relating to the enforceability of the Indentures, the Debt Securities, the Warrants and the Units, the internal laws of the State of New York.

This opinion letter deals only with the specified legal issues expressly addressed herein, and you should not infer any opinion that is not explicitly addressed herein from any matter stated in this letter.

We hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement. We also hereby consent to the use of our name under the heading “Legal Matters” in the Prospectus which forms a part of the Registration Statement. In giving this consent, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission promulgated thereunder. This opinion is expressed as of the

July 1, 2016

Page 7

date hereof unless otherwise expressly stated, and we disclaim any undertaking to advise you of any subsequent changes in the facts stated or assumed herein or of any subsequent changes in applicable laws.

Very truly yours,

/s/ Paul Hastings LLP