Exhibit 5.1

December 13, 2013

American Midstream Partners, LP

1614 15th St, Suite 300

Denver, Colorado 80202

Ladies and Gentlemen:

We have acted as counsel to American Midstream Partners, LP, a Delaware limited partnership (the “Partnership”), in connection with the proposed offering and sale by the Partnership to the Underwriter (as defined below) of up to 2,760,000 common units (including common units to be issued upon exercise of the Underwriter’s option to purchase additional common units) representing limited partner interests in the Partnership (the “Common Units”) pursuant to the Underwriting Agreement, dated December 11, 2013 (as amended on December 13, 2013, the “Underwriting Agreement”), among the Partnership, American Midstream GP, LLC, a Delaware limited liability company (the “General Partner”), American Midstream, LLC, a Delaware limited liability company (collectively with the Partnership and the General Partner, the “Partnership Parties”), and the underwriter named in Schedule I thereto (the “Underwriter”).

We have also participated in the preparation of a prospectus supplement dated December 13, 2013 (the “Prospectus Supplement”), which supplements the prospectus dated November 27, 2013 (the “Prospectus”), each forming part of the Registration Statement on Form S-3 (File No. 333-183818) (the “Registration Statement”) to which this opinion is an exhibit.  The Prospectus Supplement has been filed with the Securities and Exchange Commission (the “Commission”) pursuant to Rule 424(b) promulgated under the Securities Act of 1933, as amended (the “Securities Act”).  This opinion letter is furnished to you at your request to enable you to fulfill the requirements of Item 601(b)(5) of Regulation S-K, 17 C.F.R. § 229.601(b)(5), in connection with the Registration Statement.

As the basis for the opinion hereinafter expressed, we have examined such statutes, including the Delaware Revised Uniform Limited Partnership Act (the “Delaware Act”), partnership records and documents, certificates of company and public officials, and other instruments and documents as we deemed relevant or necessary for the purposes of the opinion set forth below, including, but not limited to, the Underwriting Agreement, the Fourth Amended and Restated Agreement of Limited Partnership of the Partnership dated as of August 9, 2013, as amended by the First Amendment thereto dated October 28, 2013 (as amended, the “Partnership Agreement”), and the Certificate of Limited Partnership of the Partnership filed with the Secretary of State of the State of Delaware.  In making our examination, we have assumed (i) that all signatures on documents examined by us are genuine, (ii) the authenticity of all documents submitted to us as originals, (iii) the conformity with the original documents of all documents submitted to us as certified, conformed, electronic or photostatic copies, (iv) that each individual signing in a representative capacity (other than on behalf of the Partnership Parties) any document reviewed by us had authority to sign in such capacity, (v) that each individual signing any document had the legal capacity to do so, (vi) that the obligations of the parties to the Underwriting Agreement (other than the Partnership Parties) are valid, binding and enforceable, (vii) the truth, accuracy and completeness of the

Holland & Hart LLP Attorneys at Law

Phone (303) 295-8000 Fax (303) 295-8261 www.hollandhart.com

555 17th Street Suite 3200 Denver, CO 80202-3979 Mailing Address Post Office Box 8749 Denver, CO 80201-8749

Aspen Billings Boise Boulder Carson City Cheyenne Colorado Springs Denver Denver Tech Center Jackson Hole Las Vegas Reno Salt Lake City Santa Fe Washington, D.C.

information, representations and warranties contained in the records, documents, instruments and certificates we have reviewed and (viii) the accuracy, completeness and authenticity of certificates of public officials.  We have also assumed the accuracy of all other information provided to us by the Partnership during the course of our investigations, on which we have relied in issuing the opinion expressed below.  We have relied upon a certificate and other assurances of officers of the General Partner and others as to factual matters without having independently verified such factual matters.  In connection with the opinion hereinafter expressed, we have assumed that all of the Common Units will be issued and sold in the manner stated in the Prospectus Supplement, the Prospectus and the Underwriting Agreement.

Based on the foregoing and on such legal considerations as we deem relevant, and subject to the qualifications, assumptions and limitations stated herein and in reliance on the statements of fact contained in the documents we have examined, we are of the opinion that, when issued and delivered on behalf of the Partnership against payment therefor by the Underwriter in accordance with the Underwriting Agreement, the issue and sale of the Common Units will have been duly authorized by all necessary partnership action of the Partnership, and the Common Units will be validly issued and, under the Delaware Act, purchasers of the Common Units will have (i) no obligation to make further payments for their purchase of the Common Units or contributions to the Partnership solely by reason of their ownership of the Common Units or their status as limited partners of the Partnership, and (ii) no personal liability for the debts, obligations or liabilities of the Partnership, whether arising in contract, tort or otherwise, solely by reason of being limited partners of the Partnership.

The opinion expressed herein is limited in all respects to the Delaware Act, and we express no opinion other than as to the Delaware Act.  We hereby consent to the reference to our firm under the caption “Legal Matters” in the Prospectus Supplement, to the filing of this opinion letter as an exhibit to the Partnership’s Current Report on Form 8-K dated on the date hereof, and to the incorporation by reference of this opinion letter into the Registration Statement.  In giving this consent, we do not admit that we are included in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission promulgated thereunder.

2