Exhibit 5.1

May 28, 2010

Genesis Energy, L.P.

919 Milam, Suite 2100

Houston, Texas 77002

Re: Genesis Energy, L.P.

Registration Statement Form S-3

Ladies and Gentlemen:

We have acted as counsel to Genesis Energy, L.P., a Delaware limited partnership (the “Partnership”), in connection with the registration, pursuant to a registration statement on Form S-3, as amended (the “Registration Statement”), filed with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Act”), relating to the offering and sale from time to time, as set forth in the Registration Statement, the form of prospectus contained therein (the “Prospectus”), and one or more supplements to the Prospectus (each, a “Prospectus Supplement”), of one or more classes or series of equity securities of the Partnership having an aggregate offering price not to exceed $750,000,000 (the “Equity Securities”), consisting of (a) common units (the “Units”) representing limited partnership interests in the Partnership, (b) other equity interests in the Partnership and options, rights, warrants and appreciation rights issued by the Partnership relating to the Units or such other equity interests (collectively, the “Other Equity Securities”), or any combination of the foregoing, each on terms to be determined at the time of each offering. We have examined originals or certified copies of the agreement of limited partnership of the Partnership as in effect on the date hereof (the “Partnership Agreement”) and such other partnership records of the Partnership and other certificates and documents of officials of the Partnership, public officials and others as we have deemed appropriate for purposes of this letter. We have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals, and the conformity to authentic original documents of all copies submitted to us as conformed and certified or reproduced copies. As to various questions of fact relevant to this letter, we have relied, without independent investigation, upon certificates of public officials and certificates of officers of the general partner of the Partnership, all of which we assume to be true, correct and complete. This opinion is being furnished at the request of the Partnership and in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Act.

Genesis Energy, L.P.

May 28, 2010

Page 2

Based upon the foregoing and subject to the assumptions, exceptions, qualifications and limitations set forth hereinafter, we are of the opinion that:

1. With respect to Equity Securities constituting Units, when (i) the Partnership has taken all necessary action to authorize and approve the issuance of such Units, the terms of the offering thereof and related matters and (ii) such Units have been issued and delivered, with certificates representing such Units having been duly executed, countersigned, registered and delivered or, if uncertificated, valid book-entry notations for the issuance thereof in uncertificated form having been duly made in the register of Units of the Partnership, in accordance with the terms of any applicable definitive purchase, underwriting or similar agreement or, if such Units are issuable upon exchange, conversion or exercise of Equity Securities constituting Other Equity Securities, the applicable instrument (“Other Equity Security Instrument”) by which the general partner of the Partnership has determined the terms (including, in the case of Partnership Securities (as defined in the Partnership Agreement), the voting powers, designations, preferences and relative, participating, optional or other special rights, duties and qualifications, limitations or restrictions) thereof, against payment (or delivery) of the consideration therefor provided for therein, such Units (including any Units duly issued upon exchange, conversion or exercise of any Other Equity Securities that are exchangeable for, convertible into or exercisable for Units) will have been duly authorized in accordance with the Partnership Agreement and validly issued and will be fully paid (to the extent required under the Partnership Agreement) and non-assessable (except for such exceptions to such non-assessability as may be described in the Registration Statement under “Description of Our Equity Securities—Our Common Units—Limited Liability” or otherwise in the Prospectus or Prospectus Supplement thereto or as may be specified in paragraph (B) below).

2. With respect to Other Equity Securities, when (i) the Partnership has taken all necessary action to authorize and approve the issuance of such Other Equity Securities, the terms of offering thereof and related matters, (ii) the general partner of the Partnership has taken all necessary partnership action to designate and establish the terms of such Other Equity Securities and has caused an Other Equity Security Instrument for such Other Equity Securities to be prepared, executed and filed with the partnership records of the Partnership and (iii) such Other Equity Securities have been issued and delivered in accordance with the terms of such Other Equity Security Instrument, with certificates representing such Other Equity Securities having been duly executed, countersigned, registered and delivered or, if uncertificated, valid book-entry notations for the issuance thereof in uncertificated form having been duly made in the register of such Other Equity Securities of the Partnership, in accordance with the terms of the applicable definitive purchase, underwriting or similar agreement or, if such Other Equity Securities are issuable upon exchange or conversion or exercise of Equity Securities constituting Other Equity Securities, the applicable Other Equity Security Instrument therefor, against payment (or delivery) of the consideration therefor provided for therein, such Other Equity Securities (including any Other

Genesis Energy, L.P.

May 28, 2010

Page 3

Equity Securities duly issued upon exchange or conversion or exercise of any Equity Securities constituting Other Equity Securities that are exchangeable for or convertible into or exercisable for Other Equity Securities) will have been duly authorized in accordance with the Partnership Agreement and (x) to the extent such Other Equity Securities constitute Partnership Securities, will be validly issued and will be fully paid (to the extent required under the Partnership Agreement) and non-assessable (except for such exceptions to such non-assessability as may be specified in paragraph (B) below) or (y) to the extent such Other Equity Securities constitute Other Equity Securities other than Partnership Securities, will be valid and binding obligations of the Partnership, enforceable against the Partnership in accordance with their terms.

The opinions and other matters in this letter are qualified in their entirety and subject to the following:

(A) We have assumed that, in the case of each offering and sale of Equity Securities, (i) the Registration Statement, and any amendments thereto (including post-effective amendments) will have become effective under the Act and such effectiveness shall not have been terminated or rescinded; (ii) a Prospectus Supplement will have been prepared and filed with the Commission describing such Equity Securities; (iii) such Equity Securities will have been issued and sold in compliance with applicable United States federal and state securities Laws (hereinafter defined) and pursuant to and in the manner stated in the Registration Statement and the applicable Prospectus Supplement; (iv) unless such Equity Securities constitute Equity Securities issuable upon exchange, conversion or exercise of Other Equity Securities, a definitive purchase, underwriting or similar agreement with respect to the issuance and sale of such Equity Securities will have been duly authorized and validly executed and delivered by the Partnership and the other parties thereto; (v) at the time of the issuance of such Equity Securities, (a) the Partnership will validly exist and be duly qualified and in good standing under the laws of its jurisdiction of formation, (b) the Partnership will have the necessary partnership power and due authorization and (c) the Partnership Agreement and the organizational or charter documents of general partner of the Partnership will be in full force and effect and will not have been amended, restated, supplemented or otherwise altered, and there will have been no authorization of any such amendment, restatement, supplement or other alteration, since the date hereof; (vi) the terms of such Equity Securities and of their issuance and sale will have been established in conformity with and so as not to violate, or result in a default under or breach of, the Partnership Agreement or other organizational document of the Partnership, and the terms of such Equity Securities and of their issuance and sale will have been established in conformity with and so as not to violate, or result in a default under or breach of any

Genesis Energy, L.P.

May 28, 2010

Page 4

applicable law, regulation or administrative order or any agreement or instrument binding upon the Partnership and so as to comply with any requirement or restriction imposed by any court or governmental or regulatory body (including any stock exchange on which the Partnership’s equity securities are listed for trading) having jurisdiction over the Partnership and, if such Equity Securities constitute Other Equity Securities, in conformity with the Other Equity Security Instrument therefor; (vii) if such Equity Securities constitute Units or other Partnership Securities, (x) sufficient such Partnership Securities will be authorized for issuance under the Partnership Agreement that have not otherwise been issued or reserved for issuance and (y) the consideration for the issuance and sale of such Partnership Securities established by the general partner of the Partnership and provided for in the applicable definitive purchase, underwriting or similar agreement (or, if such Partnership Securities are issuable upon exchange, conversion or exercise of, Other Equity Securities, the Other Equity Security Instrument therefor) will not violate the terms of the Partnership Agreement or the Delaware LP Act; (viii) if such Equity Securities constitute Equity Securities issuable upon exchange, conversion or exercise of, Other Equity Securities, the action with respect to such Other Equity Securities referred to in paragraph 2 above will have been taken; (ix) if such Equity Securities constitute Other Equity Securities that are exchangeable for or convertible into or exercisable for Equity Securities, the Partnership will have taken all necessary action to authorize and approve the issuance of such Equity Securities upon the exchange or conversion or exercise of such Other Equity Securities (including, in the case of Equity Securities (other than Units), the designation and establishment of the terms thereof pursuant to an Other Equity Security Instrument therefor that has been executed and filed with the partnership records of the Partnership), the terms of such exchange, conversion or exercise and related matters and, in the case of Partnership Securities, to reserve such Partnership Securities for issuance upon such exchange, conversion or exercise; (x) if such Equity Securities constitute Other Equity Securities other than Partnership Securities, the Other Equity Security Instrument therefor and not including any provision that is unenforceable against the Partnership will (a) have been duly authorized, executed and delivered by the Partnership and the other parties thereto and (b) constitute the valid and binding obligation of each party thereto other than the Partnership, enforceable against such party in accordance with its terms; and (xi) if such Equity Securities constitute Partnership Securities (other than Units), such Partnership Securities will constitute Limited Partner Interests (as defined in the Partnership Agreement).

Genesis Energy, L.P.

May 28, 2010

Page 5

(B) The opinions set forth in this letter are subject to the qualification that (i) under Section 17-303(a) of the Delaware Revised Uniform Limited Partnership Act (the “Delaware LP Act”), a limited partner who participates in the “control,” within the meaning of the Delaware LP Act, of the business of a partnership or takes action which constitutes “control” may be held personally liable for such partnership’s obligations under the Delaware LP Act to the same extent as a general partner and (ii) under Sections 17-303 and 17-607 of the Delaware LP Act, a limited partner who (x) receives a distribution that, at the time of distribution and after giving effect to the distribution, causes all liabilities of the Partnership, other than liabilities to partners on account of their partnership interests and non-recourse liabilities, to exceed the fair value of the assets of the limited partnership (except the fair value of property subject to a liability for which the recourse of creditors is limited, which property shall be included in the assets of the limited partnership only to the extent that the fair value of such property exceeds such liability) and (y) knew at the time of such distribution that the distribution was in violation of the Delaware LP Act shall be liable to the limited partnership for the amount of the distribution for three years from the date of the distribution.

(C) We express no opinion as to the laws of any jurisdiction other than any published constitutions, treaties, laws, rules or regulations or judicial or administrative decisions (“Laws”) of (i) the federal Laws of the United States; (ii) the Delaware LP Act; and (iii) the Limited Liability Company Act of the State of Delaware.

(D) The matters expressed in this letter are subject to and qualified and limited by (i) applicable bankruptcy, insolvency, fraudulent transfer and conveyance, reorganization, moratorium and similar laws affecting creditors’ rights and remedies generally; (ii) 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 (regardless of whether considered in a proceeding in equity or at law); and (iii) securities Laws and public policy underlying such Laws with respect to rights to indemnification and contribution.

[The remainder of this page is intentionally left blank.]

Genesis Energy, L.P.

May 28, 2010

Signature Page

We hereby consent to the filing of this letter as an exhibit to the Registration Statement and to the use of our name in the Prospectus under the caption “Legal Matters.” 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 and the rules and regulations thereunder. We also consent to your filing copies of this letter as an exhibit to the Registration Statement.

Very truly yours,

/s/ AKIN, GUMP, STRAUSS, HAUER & FELD, L.L.P.

AKIN, GUMP, STRAUSS, HAUER & FELD, L.L.P.