Exhibit 99.1

PRESS RELEASE

For information contact:
Mike Avara
Senior Vice President and Chief Financial Officer
704.973.7027
mavara@horizonlines.com

HORIZON LINES REACHES PUERTO RICO CLASS ACTION SETTLEMENT AGREEMENT AND
SUCCESSFULLY AMENDS CREDIT AGREEMENT

CHARLOTTE, N.C. (JUNE 12, 2009) — Horizon Lines, Inc. (NYSE:HRZ) today reported that it has entered into a settlement agreement with the plaintiffs in the Puerto Rico class action antitrust litigation, and also entered into a credit agreement amendment with its lender group.

Puerto Rico Class Action Settlement Agreement

As previously reported, several purported class action lawsuits were filed against Horizon Lines and other domestic shipping carriers on behalf of a class of individuals and entities who purchased domestic ocean shipping services from various domestic ocean carriers in the Puerto Rico tradelane between 2002 and 2008. Those lawsuits were consolidated into a single multidistrict litigation proceeding in the United States District Court for the District of Puerto Rico. The complaints allege price-fixing in violation of the Sherman Act and Puerto Rican antitrust laws and seek treble monetary damages, costs, attorneys’ fees, and an injunction against the allegedly unlawful conduct.

On June 11, 2009, Horizon Lines entered into a settlement agreement with the plaintiffs in the Puerto Rico class action antitrust litigation. Under the settlement agreement, which is subject to Court approval, Horizon has agreed to pay $20 million and to certain base-rate freezes, to resolve claims for alleged antitrust violations in the Puerto Rico tradelane. The payment terms would require Horizon Lines to pay into an escrow account $20 million as follows:

• $5 million within five business days following execution of a settlement agreement and submission of a motion for preliminary approval to the district court;

• $5 million within 90 days after preliminary approval of the settlement agreement by the district court; and

• $10 million within five business days after final approval of the settlement agreement by the district court.

The base-rate freeze component of the settlement agreement provides that class members who have contracts in the Puerto Rico trade with Horizon Lines as of the effective date of the settlement would have the option, in lieu of receiving cash, to have their “base rates” frozen for a period of two years. The base-rate freeze would run for two years from the expiration of the contract in effect on the effective date of the settlement. All class members would be eligible to

share in the $20 million cash component, but only contract customers of Horizon Lines would be eligible to elect the base-rate freeze in lieu of receiving cash.

The settlement agreement is subject to Court approval. In addition, Horizon Lines has the right to terminate the settlement agreement under certain circumstances.

As previously reported, Horizon Lines received a grand jury subpoena and search warrant from the U.S. District Court for the Middle District of Florida seeking information regarding an investigation by the Antitrust Division of the U.S. Department of Justice into possible antitrust violations in the domestic ocean shipping business, including Puerto Rico. Horizon Lines is cooperating with the Antitrust Division in that investigation. Also, several class action lawsuits relating to ocean shipping services in the Hawaii and Guam tradelanes and the Alaska tradelane have been filed against Horizon Lines. Horizon Lines intends to vigorously defend itself against those purported class action lawsuits.

Credit Agreement Amendment

Horizon Lines also reached an agreement with its lenders to amend the existing credit agreement in conjunction with the Puerto Rico settlement.

The agreement will amend the definition of Consolidated EBITDA by:

• Adding certain charges related to the Puerto Rico settlement back to to the calculation of Consolidated EBITDA, and

• Adding certain charges for litigation expenses related to antitrust litigation matters in an amount not to exceed $25 million in the aggregate and $15 million over a 12-month period back to the calculation of Consolidated EBITDA.

The definition of Consolidated EBITDA is used to determine whether Horizon Lines is in compliance with its secured leverage ratio and interest coverage ratio, as well as its ability to make certain restricted payments.

As consideration for the amendment, Horizon Lines has agreed to provide the following economic and structural changes for the benefit of the lenders:

• Increase loan and letter of credit pricing by 150bps and an increase in the commitment fee;

• A reduction in the size of the revolving facility from $250 million to $225 million;

• The elimination of the $150 million incremental facility;

• An amendment to the definition of Consolidated EBITDA that clarifies “non-recurring charges”; and

• Other structural enhancements, including a step-down in the secured leverage ratio and further limitations on the ability to make certain restricted payments.

In addition, Horizon Lines has agreed to pay consent fees of $1.8 million. A copy of the Credit Agreement amendment is filed as an exhibit to a current report that Horizon Lines filed with the SEC on June 12, 2009.

‘We appreciate the support of our lender group in the amendment process that provided the clarity and flexibility necessary to effect this settlement,” said Mike Avara, Senior Vice President and Chief Financial Officer. “Although the cost of debt on both our $150 million revolver balance and $115.6 million term loan outstanding as of June 11^th has increased by 1.50%, our revised blended total cost of debt remains fairly low at 4.47%, up from the previous 3.81%. The 4.25% interest rate on our convertible notes remains unchanged. We have worked closely with our banks and expect to remain in compliance with our financial covenants,” said Mike Avara.

About Horizon Lines

Horizon Lines, Inc. is the nation’s leading domestic ocean shipping and integrated logistics company comprised of two primary operating subsidiaries. Horizon Lines, LLC, owns or leases a fleet of 21 U.S.-flag containerships and operates 5 port terminals linking the continental United States with Alaska, Hawaii, Guam, Micronesia and Puerto Rico. Horizon Logistics, LLC, offers customized logistics solutions to shippers from a suite of transportation and distribution management services, information technology developed by Horizon Services Group and intermodal trucking and warehousing services provided by Sea-Logix. 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 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 performance, achievements or events. Words such as, but not limited to, “believe,” “expect,” “anticipate,” “estimate,” “intend,” “plan,” “target,” “projects,” “likely,” “will,” “would,” “could,” and similar expressions or phrases identify forward-looking statements.

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 February 5, 2009, 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 developments anticipated by us will be realized or, even if substantially realized, that they will have the expected consequences.