Exhibit 99.1

PRESS RELEASE

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

HORIZON LINES REACHES AGREEMENT WITH CONVERTIBLE NOTE HOLDERS
FOR COMPLETE REFINANCING

Consummation of Transaction Expected in August

CHARLOTTE, NC, June 1, 2011 — Horizon Lines, Inc. (NYSE: HRZ) today announced that it and holders of the majority of its 4.25% convertible senior notes have entered into agreements for a transaction that will refinance the company’s entire capital structure.

The agreement with the note holders contemplates a complete refinancing, in conjunction with a new asset-based revolving loan facility (ABL) of up to $125 million, which is under negotiation with a leading financial institution.

The company’s current debt structure consists of a $225 million senior secured revolving credit facility, a $125 million secured term loan, and $330 million of unsecured 4.25% convertible senior notes.

The recapitalization will eliminate the refinancing risk related to the maturity of the existing convertible notes and the existing bank debt in 2012, and will provide liquidity to fund continued operations through the new senior secured notes and new ABL Facility. At the same time, the recapitalization provides for the immediate deleveraging of the balance sheet by $50 million through a debt-for-equity exchange and provides the potential for additional deleveraging through the early conversion of the new convertible secured notes to be issued in the exchange offer.

During and after the recapitalization process, the company intends to conduct business as usual throughout its tradelanes, focusing on continued customer service excellence and operational efficiencies.

Consummation of the refinancing is expected to occur in August, following finalization of documentation and completion of the exchange offer for the company’s existing 4.25% convertible senior notes, which by law requires 20 business days to execute.

Horizon Lines Refinancing Agreement		Page 2 of 4

The agreements provide that the company will sell to certain qualified institutional buyers new first-lien $350 million, 9.0% senior secured notes due five years from the date of issuance. The company will have the right to redeem the new 9.0% notes without paying a premium at any time between closing and maturity.

The agreements also provide that the company will offer to exchange the existing $330 million of unsecured 4.25% convertible senior notes for:

	•		a new series of $200 million 6.0% convertible secured notes, maturing in five and a half years and convertible into common stock at $1.70 per share;
	•		a cash payment of $80 million; and
	•		approximately 38.5 million shares of common stock, which would comprise about 56% of the outstanding capital stock of the company at closing.

In addition, the company is expected to have the right to convert the new 6.0% convertible secured notes, beginning three months after the issuance, in increments not to exceed $50 million. The 30-day weighted average price of the stock must be at least $2.00 on the first conversion date. The subsequent 30-day weighted average price of the stock must be at least $2.10 on the second conversion date, $2.30 on the third, and $2.40 on the fourth and final conversion date, and each subsequent conversion date must be at least three months after the previous conversion date.

Pursuant to the agreements, the company expects to complete the exchange offer of the existing unsecured 4.25% convertible senior notes in August, and must also complete the offering of the new 9.0% senior secured notes and enter into the ABL facility. The company also has agreed not to pursue any other restructuring alternatives.

A copy of the form of support agreement from each of the note holders will be included as an exhibit to a form 8-K that Horizon Lines will be filing with the SEC.

The agreements do not constitute a commitment by any of the existing holders of the unsecured 4.25% convertible senior notes to lend money to the company or to purchase any new debt securities issued by the company, including the new first-lien $350 million, 9.0% senior secured notes.

The description of terms set forth above is subject to change based upon the negotiations by the parties, and the final transactions, if any, may include terms that are materially different than those terms described above or otherwise described in the support agreements. The support agreements are subject to various contingencies and the company offers no assurances that it will be able to execute the transactions as described in the support agreements or any other transaction.

None of the securities that the company expects to offer or sell pursuant to the support agreement have been or will be registered under the United States Securities Act of 1933,

Horizon Lines Refinancing Agreement		Page 3 of 4

as amended (the “Act”), and none of them may be offered or sold in the United States absent registration or applicable exemption from the registration requirements of the Act.

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,” “intend,” “expect,” “would,” “could,” “must,” “may,” 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: the ability of the parties to agree on the final terms of the refinancing; our ability to close on the refinancing; NYSE permitting us to issue the equity securities without a shareholder vote; our ability to satisfy other conditions of the refinancing; the ability of the investors to fund the refinancing; general conditions in the capital markets; general economic conditions; our ability to maintain adequate liquidity to operate our business; 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

Horizon Lines Refinancing Agreement		Page 4 of 4

harm our results. Consequently, there can be no assurance that actual results or developments anticipated by us will be realized or, even if substantially realized, that they will have the expected consequences.

# # #