Exhibit 5.1

2001 ROSS AVENUE
DALLAS, TEXAS
75201-2980

TEL    +1
214.953.6500
FAX    +1
214.953.6503
www.bakerbotts.com AUSTIN
DALLAS
DUBAI
HONG KONG
HOUSTON
LONDON
MOSCOW
NEW YORK
RIYADH
WASHINGTON

December 18, 2007

Martin Midstream Partners L.P.
Martin Operating Partnership L.P.
4200 Stone Road
Kilgore, Texas 75662

Ladies and Gentlemen:

     We have acted as counsel for Martin Midstream Partners L.P., Delaware limited partnership (the “Partnership”), and Martin Operating Partnership L.P., a Delaware limited partnership (the “Operating Partnership”), with respect to certain legal matters in connection with the filing with the Securities and Exchange Commission (the “Commission”) of a registration statement (the “Registration Statement”) under the Securities Act of 1933, as amended (the “Securities Act”), registering securities to be issued and sold by the Partnership and/or the Operating Partnership from time to time pursuant to Rule 415 under the Securities Act for an aggregate initial offering price not to exceed $400,000,000. Such securities include (i) common units representing limited partner interests in the Partnership (the “Common Units”); (ii) unsecured debt securities of the Partnership, in one or more series, consisting of notes, debentures or other evidences of indebtedness (the “Partnership Debt Securities”); (iii) unsecured debt securities of the Operating Partnership, in one or more series, consisting of notes, debentures or other evidences of indebtedness (the “Operating Partnership Debt Securities” and, together with the Partnership Debt Securities, the “Debt Securities”); and (iv) guarantees (the “Guarantees”) of such Debt Securities by the Partnership and/or the Operating Partnership. The Common Units, the Debt Securities and the Guarantees are collectively referred to herein as the “Securities.”

     In connection therewith, we have examined (i) the First Amended and Restated Agreement of Limited Partnership of the Partnership and the Certificate of Limited Partnership of the Partnership, each as amended to date, (ii) the Amended and Restated Agreement of Limited Partnership of the Operating Partnership and the Certificate of Limited Partnership of the Operating Partnership, each as amended to date, (iii) the Limited Liability Company Agreement of Martin Midstream GP LLC, a Delaware limited liability company and the general partner of the Partnership (the “General Partner”), and the Certificate of Formation of the General Partner, each as amended to date, (iv) the Limited Liability Company Agreement of Martin Operating GP LLC, a Delaware limited liability company and the general partner of the Operating Partnership (the “Operating General Partner”), and the Certificate of Formation of the Operating General Partner, each as amended to date, (v) the forms of each of the Partnership’s and the Operating Partnership’s senior and subordinated indentures filed as exhibits to the Registration Statement (collectively, the “Indentures”), (vi) partnership and limited liability company records of the Partnership, the Operating Partnership, the General Partner and the Operating General Partner, including minute books of the General Partner as furnished to us by

Martin Midstream Partners L.P. 2 December 18, 2007

the General Partner, and (vii) the originals, or copies certified or otherwise identified to our satisfaction, of certificates of public officials and of representatives of the Partnership, the Operating Partnership, the General Partner and the Operating General Partner, and such other instruments and documents as we have deemed necessary, and (viii) the Registration Statement and the prospectus contained therein (the “Prospectus”) as a basis for the opinions hereafter expressed.

     In connection with this opinion, we have assumed that (i) the Registration Statement and any amendments thereto (including post-effective amendments) will have become effective; (ii) a prospectus supplement will have been prepared and filed with the Commission describing the Securities offered thereby; (iii) all Securities will be issued and sold in compliance with applicable federal and state securities laws and in the manner stated in the Registration Statement, the Prospectus and the appropriate prospectus supplement; (iv) a definitive purchase, underwriting or similar agreement with respect to any Securities offered will have been duly authorized and validly executed and delivered by the Partnership, the Operating Partnership, the General Partner and/or the other parties thereto; (v) any securities issuable upon conversion, redemption, exchange or exercise of any Securities being offered will be duly authorized, created and, if appropriate, reserved for issuance upon such conversion, redemption, exchange or exercise; (vi) the certificates for any other offered Securities will conform to the specimens thereof examined by us and will have been duly countersigned and/or registered by the applicable transfer agent, and/or transfer for such Securities; and (vii) each document submitted to us for review is accurate and complete, each such document that is an original is authentic, each such document that is a copy conforms to an authentic original and all signatures on each such document are genuine.

     Based upon and subject to the foregoing, we are of the opinion that:

     1. With respect to Common Units, when (a) the Partnership has taken all necessary action to approve the issuance of such Common Units, the terms of the offering thereof and related matters and (b) such Common Units have been issued and delivered in accordance with the terms of the applicable definitive purchase, underwriting or similar agreement approved by the Partnership upon payment of the consideration therefor provided for therein, such Common Units will be duly authorized and validly issued and will be fully paid and nonassessable except as such nonassessability may be effected by the matters below:

     (a) If a court were to determine, that the right, or the exercise of the right, under the First Amended and Restated Agreement of Limited Partnership of the Partnership (the “Partnership Agreement”) by the holders of the Common Units and subordinated units (the “Limited Partners”) of the Partnership as a group (i) to remove or replace the General Partner, (ii) to approve certain amendments to the Partnership Agreement, or (iii) to take certain other actions under the Partnership Agreement, constitutes “participation in the control” of the Partnership’s business for the purposes of the Delaware Uniform Revised

Martin Midstream Partners L.P. 3 December 18, 2007

Limited Partnership Act (the “Act”), then the Limited Partners could be held personally liable for the Partnership’s obligations under the laws of Delaware, to the same extent as the General Partner with respect to persons who transact business with the Partnership reasonably believing, based on the conduct of any of the Limited Partners, that such Limited Partner is a general partner.

     (b) Section 17-607 of the Delaware Act provides that a Limited Partners who receives a distribution and knew at the time of the distribution that it was made in violation of the Delaware Act shall be liable to the Partnership for three years for the amount of the distribution.

     2. With respect to the Debt Securities and/or the Guarantees to be issued under the applicable Indenture, when (a) the applicable Indenture has been duly authorized and validly executed and delivered by the Partnership, the Operating Partnership and/or the trustee thereunder, (b) the applicable Indenture has been duly qualified under the Trust Indenture Act of 1939, as amended, (c) the Partnership and/or the Operating Partnership have taken all necessary action to approve the issuance and terms of such Debt Securities and/or Guarantees, the terms of the offering thereof and related matters and (d) such Debt Securities and Guarantees have been duly executed, authenticated, issued and delivered in accordance with the terms of the applicable Indenture and the applicable definitive purchase, underwriting or similar agreement approved by the Partnership and/or the Operating Partnership upon payment of the consideration therefor provided for therein, such Debt Securities and/or Guarantees will be duly authorized and legally issued and will constitute valid and legally binding obligations of the Partnership and/or the Operating Partnership, enforceable against the Partnership and/or the Operating Partnership in accordance with their terms, except as the enforceability thereof may be limited by (i) bankruptcy, insolvency, reorganization, moratorium, fraudulent conveyance or other similar laws relating to or affecting creditors’ rights generally, (ii) general principles of equity (regardless of whether such enforceability is considered in a proceeding in equity or at law) or (iii) any implied covenants of good faith and fair dealing.

     The opinions set forth above are limited in all respects to matters of the laws of the State of New York, the Delaware Revised Uniform Limited Partnership Act, the Delaware Limited Liability Company Act and applicable federal law.

     We hereby consent to the filing of this opinion as Exhibit 5.1 to the Registration Statement. We also consent to the reference to our Firm under the heading “Legal Matters” in the Prospectus. In giving this consent, however, we do not hereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission thereunder.

Martin Midstream Partners L.P. 4 December 18, 2007

Very truly yours,

/s/  Baker Botts LLP