Exhibit 99.1

MARTIN MIDSTREAM PARTNERS L.P.
RECEIVES FAVORABLE PRIVATE LETTER RULING
FROM INTERNAL REVENUE SERVICE
ON MARINE TIME CHARTERS

KILGORE, Texas, Mar 11, 2010 (GlobeNewswire via COMTEX News Network) — Martin Midstream Partners L.P. (Nasdaq:MMLP) announced today it has received a favorable ruling from the United States Internal Revenue Service (IRS) regarding the tax characterization of income derived from its marine time charter agreements as qualifying transportation income. On January 29, 2010, MMLP announced that it was seeking such a ruling after having become aware of a specific decision by the United States Court of Appeals for the Fifth Circuit in which gross income derived by another entity from its time charters was deemed to be rental income, rather than transportation income, and thus created some uncertainty as to whether the Partnership will continue to be classified as a partnership for U.S. federal income tax purposes.

In order for the Partnership to be classified as a partnership for U.S. federal income tax purposes, at least 90% of its gross income each year must be “qualifying income” under Section 7704 of the U.S. Internal Revenue Code of 1986, as amended. Section 7704(d)(1)(E) defines “qualifying income” to include income and gains from the exploration, development, mining or production, processing, refining, transportation, or marketing of any mineral or natural resource. In the ruling we obtained, the IRS concluded that the income MMLP derives from transporting crude oil, refined petroleum products, and other qualifying products under Section 7704(d)(1)(E) of the Internal Revenue Code pursuant to its marine time charter agreements is qualifying income. Although this ruling is generally binding on the IRS, the continuing validity of the ruling will be subject to the continuing accuracy of factual representations and assumptions made by MMLP in its ruling request.

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. The Partnership’s primary business lines include: terminalling and storage services for petroleum products and by-products; natural gas gathering and processing and NGL distribution services; sulfur and sulfur-based products processing, manufacturing, marketing and distribution; and marine transportation services for petroleum products and by-products.

Forward-Looking Statements

Statements about Martin Midstream Partners’ outlook and all other statements in this release other than historical facts are forward-looking statements within the meaning of the Private Securities Litigation Reform Act of 1995. These forward-looking statements and all references to financial estimates rely on a number of assumptions concerning future events and are subject to a number of uncertainties and other factors, many of which are outside its control, which could cause actual results to differ materially from such statements. While MMLP believes that the

assumptions concerning future events are reasonable, it cautions that there are inherent difficulties in anticipating or predicting certain important factors. A discussion of these factors, including risks and uncertainties, is set forth in the Partnership’s annual and quarterly reports filed from time to time with the Securities and Exchange Commission. Martin Midstream Partners disclaims any intention or obligation to revise any forward-looking statements, including financial estimates, whether as a result of new information, future events, or otherwise.

Additional information concerning Martin Midstream is available on its website at www.martinmidstream.com, or

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