Exhibit 99.1

FOR IMMEDIATE RELEASE

MARTIN MIDSTREAM PARTNERS L.P. ANNOUNCES
CHARLES HENRY “HANK” STILL AS NEW
DIRECTOR OF GENERAL PARTNER’S BOARD,
PARTNERSHIP RECEIVES NASDAQ LISTING COMPLIANCE NOTIFICATION

KILGORE, TX, July 29, 2010 (GlobalNewswire via COMTEX News Network) — Martin Midstream Partners L.P. (NASDAQ: MMLP) (“MMLP”) announces the appointment of Charles Henry “Hank” Still as a new member of the board of directors of Martin Midstream GP LLC (the “General Partner”), which is the general partner of MMLP.

Mr. Still, age 67, is a partner and head of the Houston corporate practice group in the law firm Kelly Hart & Hallman LLP, having more than 40 years of experience in multiple aspects of corporate law. Prior to joining Kelly Hart & Hallman LLP in 2008, Mr. Still was an associate and partner in the law firm Fulbright & Jaworski L.L.P. from 1968 until his retirement in 2008. Mr. Still is currently on the board of directors of OYO Geospace Corporation. Mr. Still holds a J.D. from the University of Texas School of Law and a B.B.A. in accounting from Texas Tech University. He is also an Adjunct Professor of Law at the University of Texas School of Law.

Ruben Martin, President and Chief Executive Officer of the General Partner said, “We are pleased to welcome Hank to the Board. His diverse industry experience and legal background in corporate and partnership matters will serve MMLP and its unit holders well. Hank will bring a fresh perspective to the Board.”

Mr. Still is an independent director as defined under The NASDAQ Stock Market, LLC (“Nasdaq”) listing standards and applicable SEC rules and otherwise meets the additional Nasdaq listing standards requirements for audit committee membership. Accordingly, on July 27, 2010, Mr. Still was appointed to serve on the audit committee of the General Partner.

On July 27, 2010, MMLP communicated to Nasdaq the appointment of Mr. Still to the board of directors and the audit committee of the General Partner and Mr. Still’s qualifications under Nasdaq listing standards. MMLP further communicated that, as a result of Mr. Still’s appointment to the audit committee, MMLP has regained compliance with Nasdaq Listing Rule 5605(c)(2)(A). In response, Nasdaq issued a letter to MMLP on July 28, 2010, confirming that MMLP had regained compliance with Nasdaq Listing Rule 5605.

About Martin Midstream Partners L.P. (NASDAQ: MMLP)

Martin Midstream Partners is a publicly traded limited partnership with a diverse set of operations focused primarily in the United States Gulf Coast region. MMLP’s primary business lines include: terminalling and storage services for petroleum products and by-products; natural gas gathering and processing and NGL distribution services; and sulfur and sulfur-based products processing, manufacturing, marketing and distribution; marine transportation services for petroleum products and by-products.

Additional information concerning MMLP is available on its website at www.martinmidstream.com.

Contact: Joe McCreery, Head of Investor Relations,
Martin Midstream Partners L.P.
Phone: (903) 812-7989
joe.mccreery@martinmlp.com