Exhibit 99.1

For information contact:
Jim Storey
Director, Investor Relations & Corporate Communications
704.973.7107
jstorey@horizonlines.com

HORIZON LINES RECEIVES NOTICE REGARDING NYSE LISTING CRITERIA

CHARLOTTE, NC, May 31, 2011 — Horizon Lines, Inc. (NYSE: HRZ) today announced that the New York Stock Exchange (NYSE) has notified the company that it has fallen below the NYSE’s continued listing standards related to minimum market capitalization in combination with stockholders’ equity.

Horizon Lines is considered below continued listing criteria established by the NYSE because the company’s market capitalization averaged less than $50 million over a consecutive 30 trading-day period at the same time that stockholders’ equity was below $50 million. According to NYSE continued listing criteria, a NYSE-listed company must maintain average market capitalization of not less than $50 million over a 30 trading-day period or stockholders’ equity of not less than $50 million. Horizon Lines’ stockholders’ equity was below $50 million in its most recent 10-Q filed with the Securities and Exchange Commission on April 29, 2011, for the quarter ended March 27, 2011.

Horizon Lines has notified the NYSE that it will submit a plan to restore compliance. The company has 45 days from receipt of the May 24, 2011 notice to submit a plan and the NYSE has 45 days from receipt of the plan to accept or reject it. If the plan is accepted, the company has up to 18 months to demonstrate compliance with the NYSE continued listing standards. During this 18-month period, the company’s shares will continue to be listed and traded on the NYSE, subject to compliance with other NYSE continued listing standards.

The company is currently in discussions to refinance its debt and, as part of the plan to restore compliance, it hopes that a successful refinancing outcome, if achieved, will help cure the deficiency.

“Our objective is to secure a comprehensive refinancing” said Stephen H. Fraser, President and Chief Executive Officer. “We believe our current stock price and market capitalization reflect investor concern over our ability to achieve a long-term refinancing that deleverages the company and preserves equity. We are working toward a refinancing which we hope will alleviate that concern and help us achieve higher market capitalization.

Horizon Lines 1st Quarter 2011		Page 2 of 3

About Horizon Lines

Horizon Lines, Inc. is the nation’s leading domestic ocean shipping and integrated logistics company. The company owns or leases a fleet of 20 U.S.-flag containerships and operates five port terminals linking the continental United States with Alaska, Hawaii, Guam, Micronesia and Puerto Rico. The company provides express trans-Pacific service between the U.S. West Coast and the ports of Ningbo and Shanghai in China, manages a domestic and overseas service partner network and provides integrated, reliable and cost competitive logistics solutions. Horizon Lines, Inc., is based in Charlotte, NC, and trades on the New York Stock Exchange under the ticker symbol HRZ.

Forward Looking Statements

The information contained in this press release should be read in conjunction with our filings made with the Securities and Exchange Commission. This press release contains “forward-looking statements” within the meaning of the federal securities laws. These forward-looking statements are intended to qualify for the safe harbor from liability established by the Private Securities Litigation Reform Act of 1995. Forward-looking statements are those that do not relate solely to historical fact. They include, but are not limited to, any statement that may predict, forecast, indicate or imply future results, performance, achievements or events. Words such as, but not limited to, “will,” “hope”, “intend”, “may,” “expect,” and similar expressions or phrases identify forward-looking statements.

Factors that may cause expected results or anticipated events or circumstances discussed in this press release to not occur or to differ from expected results include: our ability to successfully complete a refinancing, our ability to maintain adequate liquidity to operate our business; our ability to continue to comply with other NYSE listing standards applicable to our common stock, including maintaining a market capitalization of at least $15 million and the 30 day average of our common stock price remaining above $1.00; our ability to execute any plan submitted to the NYSE and demonstrate our compliance with the plan; volatility in equity markets in the United States; volatility in fuel prices and in freight rates; decreases in shipping volumes; or our ability to continue as a going concern.

All forward-looking statements involve risk and uncertainties. In light of these risks and uncertainties, expected results or other anticipated events or circumstances discussed in this press release might not occur. We undertake no obligation, and specifically decline any obligation, to publicly update or revise any forward-looking statement, whether as a result of new information, future events or otherwise. See the section entitled “Risk Factors” in our Form 10-K filed with the SEC on March 28, 2011, for a more complete discussion of these risks and uncertainties and for other risks and uncertainties. Those factors and the other risk factors described therein are not necessarily all of the important factors that could cause actual results or developments to differ materially from those expressed in any of our forward-looking statements. Other unknown or unpredictable factors also could harm our results. Consequently, there can be no assurance that actual results or

Horizon Lines 1st Quarter 2011		Page 3 of 3

developments anticipated by us will be realized or, even if substantially realized, that they will have the expected consequences.

# # #