Exhibit 8.1

2200 Ross Avenue, Suite 2200 Dallas, TX 75201 Telephone: 214-740-8000 Fax: 214-740-8800 www.lockelord.com

August 22, 2012

Martin Midstream Partners L.P.

4200 Stone Road

Kilgore, Texas 75662

Ladies and Gentlemen:

We have acted as counsel to Martin Midstream Partners L.P., a Delaware limited partnership (the “Partnership”), with respect to certain legal matters in connection with the offer and sale by the Partnership of its common units representing limited partner interests (the “Common Units”). We have also participated in the preparation of the Partnership’s Registration Statement on Form S-3, dated August 22, 2012 (the “Registration Statement”) and related prospectus in connection therewith (the “Prospectus”).

In connection therewith, we prepared the discussion set forth under the caption “Material Tax Considerations” in the Prospectus (the “Discussion”).

We hereby confirm that all statements of legal conclusions contained in the Discussion reflect the opinion of Locke Lord LLP with respect to the matters set forth therein as of the date of the Prospectus, subject to the assumptions, qualifications, exceptions and limitations set forth therein, and excepting the representations and statements of fact of the Partnership and its general partner included in the Discussion, as to which we express no opinion.

In providing this opinion, we have examined and are relying upon the truth and accuracy at all relevant times of the statements, covenants, and representations contained in (i) the Registration Statement and Prospectus, (ii) certain other filings made by the Partnership with the Securities and Exchange Commission (“SEC”) and (iii) other information provided to us by the Partnership and its general partner.

This opinion is furnished to you, and is for your use in connection with the transactions set forth in the Registration Statement. This opinion may not be relied upon by you for any other purpose or furnished to, assigned to, quoted to or relied upon by any other person, firm or other entity, for any purpose, without our prior written consent. However, this opinion may be relied upon by you and by persons entitled to rely on it pursuant to applicable provisions of federal securities law, including persons purchasing Common Units pursuant to the Registration Statement.

Atlanta, Austin, Chicago, Dallas, Hong Kong, Houston, London, Los Angeles, New Orleans, New York, Sacramento, San Francisco, Washington DC

August 22, 2012

Page 2

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement on Form S-3 and to the use of our name in the Discussion in the Prospectus. In giving this consent, we do not hereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the SEC thereunder.

Very truly yours,

/s/ Locke Lord LLP

LOCKE LORD LLP