Exhibit 5.1

June 27, 2016

Genesis Energy, L.P.

919 Milam, Suite 2100

Houston, Texas 77002

Registration Statement on Form S-3

File No. 333-195858

Ladies and Gentlemen:

We have acted as counsel to Genesis Energy, L.P., a Delaware limited partnership (the “Partnership”), in connection with (i) the registration, pursuant to a Registration Statement on Form S-3 (File No. 333-195858, the “Registration Statement”), filed with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Act”), of the offering and sale by the Partnership of units of the Partnership’s Common Units – Class A representing limited partner interests in the Partnership (the “Common Units”), and (ii) the preparation of a prospectus supplement, dated June 27, 2016, to be filed on the date hereof with the Commission pursuant to Rule 424(b)(5) under the Act (the “Prospectus Supplement”), which supplements the base prospectus contained in the Registration Statement, in connection with the offering and sale from time to time on a delayed or continuous basis pursuant to Rule 415(a)(4) of the Act by the Partnership of Common Units having an aggregate offering price not to exceed $400,000,000 (the “Partnership Units”), pursuant to the terms of an equity distribution agreement (the “Equity Distribution Agreement”), dated June 27, 2016, among the Partnership, with RBC Capital Markets, LLC, BNP Paribas Securities Corp., Capital One Securities, Inc., Deutsche Bank Securities Inc., DNB Markets, Inc., Fifth Third Securities, Inc., Scotia Capital (USA) Inc. and SMBC Nikko Securities America, Inc. Capitalized terms not defined herein shall have the meanings ascribed to them in the Equity Distribution Agreement. This opinion is being furnished in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Act.

We have examined originals or certified copies of such corporate 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 legal capacity of all natural persons, the authenticity of all documents submitted to us as originals and the conformity to authentic original documents of all

1111 Louisiana Street, 44th Floor | Houston, Texas 77002-5200 | 713.220.5800 | fax: 713.236.0822 | akingump.com

Genesis Energy, L.P.

June 27, 2016

Page 2

copies submitted to us as conformed, certified or reproduced copies. We have also assumed that (i) the Partnership Units will be issued and sold pursuant to the Registration Statement in such manner as relates to and is described in the Prospectus Supplement and in accordance with the terms of the Equity Distribution Agreement; and (ii) upon sale and delivery, the certificates for the Partnership Units will conform to the specimen thereof filed as an exhibit to the Registration Statement and will have been duly countersigned by the transfer agent and duly registered by the registrar for the Common Units or, if uncertificated, valid book-entry notations for the issuance of the Partnership Units in uncertificated form will have been duly made in the Common Unit register of the Partnership. 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 Partnership, all of which we assume to be true, correct and complete.

Based upon the foregoing, and subject to the assumptions, exceptions, qualifications and limitations set forth herein, we are of the opinion that, when the Partnership Units have been issued and delivered in accordance with the Equity Distribution Agreement against payment in full of the consideration payable therefor as determined by the Board of Directors of the General Partner or a duly authorized committee thereof and as contemplated by the Equity Distribution Agreement, (a) the Partnership Units will be duly authorized and validly issued and (b) holders of the Partnership Units will have no obligation to make any further payments to the Partnership for the issuance of the Partnership Units or contributions to the Partnership solely by reason of their ownership of the Partnership Units, except for their obligations to repay any funds wrongfully distributed to them.

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

We hereby consent to the filing of this opinion as an exhibit to a Current Report on Form 8-K to be filed by the Partnership with the Commission on or about the date hereof, to the incorporation by reference of this opinion into the Registration Statement and to the use of our

Genesis Energy, L.P.

June 27, 2016

Page 3

name in the Prospectus Supplement 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.