Exhibit 99.1

PRESS RELEASE

For information contact:

HORIZON LINES TO DISCONTINUE TRANS-PACIFIC FSX SERVICE

Company Will Conduct Orderly Transition to Minimize Supply Chain Disruptions

Last Voyage of FSX Service from China Expected on November 2;

Final Sailings to Guam on November 8 and 10

CHARLOTTE, NC (October 24, 2011) – Horizon Lines, Inc. (OTCQB: HRZL), the nation’s leading domestic ocean shipping company, today announced it will discontinue its Five Star Express (FSX) trans-Pacific container shipping service between the U.S. West Coast, Guam and China.

Horizon is implementing an orderly transition plan, beginning October 31, 2011, and will work aggressively to mitigate any supply chain disruptions for its customers. Discontinuation of the FSX Guam and China services will have no impact on the company’s domestic ocean services in Alaska, Hawaii, or Puerto Rico.

“This has been a very difficult decision in light of the tremendous contributions from our associates, and our organized labor and vendor partners, who have worked so hard to make the FSX service a success,” said Stephen H. Fraser, President and Chief Executive Officer. “Our decision to exit this highly volatile market will allow Horizon to focus on our core domestic ocean shipping services, and provide the opportunity to produce a more profitable and stable financial performance over time.”

The last voyage of the FSX service from China is scheduled to depart Shanghai on November 2, 2011. Horizon Lines also will suspend ocean services to Guam and surrounding islands effective with the last sailing from the U.S. West Coast on November 10, 2011.

The company expects to cease all operations related to the FSX service during the fourth quarter and does not expect to have significant continuing involvement in the operations after the termination. Therefore, the company will classify the FSX service as discontinued operations and as a result, expects to record a pretax restructuring charge of between $105 million and $110 million in fiscal fourth quarter 2011. The charge includes estimated costs to return excess rolling stock equipment, facility closures, severance, and vessel charter

expense, net of estimated sub-charter income. Losses associated with the FSX service produced a negative adjusted EBITDA impact of approximately $43.7 million for the nine months ended September 25, 2011, with additional losses expected through the end of the year.

Following their last voyages, the five Hunter-Class D-8 vessels operating in the FSX service are currently planned to be laid up, after dry-docking of the remaining four vessels. The vessels are leased from Ship Finance International Limited through 2018 to 2019. Horizon Lines is exploring sub-chartering the vessels and other solutions to partially mitigate ongoing charter expense and maintenance costs.

Horizon Lines launched the FSX service in December 2010, following expiration of a long-term space charter agreement with Maersk Line. The FSX service offers rapid eastbound transit between Ningbo and Shanghai in China and Los Angeles and Oakland on the U.S. West Coast. The westbound leg of the FSX service provides transit between the U.S. West Coast, Guam, Micronesia and the Northern Mariana Islands.

Since early in the year, the FSX service met volume and vessel utilization expectations, winning cargo from customers attracted to the schedule reliability, rapid ocean transit and seamless intermodal rail links to inland U.S. cities. However, the Shanghai Container Freight Index cites eastbound freight rates from China to the United States have fallen more than 37% in the past 12 months, from $2,400 per 40-foot container in October 2010 to approximately $1,500 in October of this year, the lowest level since the worldwide recession of 2008-2009. At the same time, the average price of bunker fuel has climbed more than 40% since the launch of the service.

“We do not expect any measurable improvements in fuel prices, the freight-rate environment or in this tradelane for the foreseeable future,” said Brian Taylor, Executive Vice President and Chief Operating Officer. “Growing capacity continues to outpace demand and the forecast for 2012 calls for more of the same.”

In Guam, the expected growth in cargo driven by infrastructure improvements associated with the military redeployment from Okinawa has been further delayed due to the budget crises in Japan and the U.S., as well as revised Japanese priorities in the wake of the earthquake and tsunami earlier this year. This has made the Guam trade no longer financially viable for Horizon Lines, without an eastbound return voyage from China.

“Given current market conditions and foreseeable future expectations, discontinuing the FSX service is the appropriate decision for the company,” said Mr. Taylor. “It will allow us to focus all of our resources on serving customers in the very solid domestic ocean markets in Alaska, Hawaii and Puerto Rico.”

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 and Puerto Rico. The company also provides integrated, reliable and cost competitive logistics solutions. Horizon Lines, Inc., is based in Charlotte, NC, and trades on the OTCQB Marketplace under symbol HRZL.

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. 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: volatility in fuel prices; the cyclical nature of international shipping industry and resulting volatile changes in freight rates; decreases in shipping volumes; our ability to maintain adequate liquidity to operate our business; our ability to service our substantial debt; any new adverse developments relating to antitrust matters in any of our trades; suspension or debarment by the federal government; compliance with safety and environmental protection and other governmental requirements; increased inspection procedures and tighter import and export controls; repeal or substantial amendment of the coastwise laws of the United States, also known as the Jones Act; our ability to remain Jones Act compliant because of changes in ownership; catastrophic losses and other liabilities; the arrest of our vessels by maritime claimants; and severe weather and natural disasters.

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. The forward-looking statements included in the press release are made only as of the date they are made and the company undertakes no obligation to update any such statements, except as otherwise required by applicable law. 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 developments anticipated by us will be realized or, even if substantially realized, that they will have the expected consequences.

# # #