Exhibit 99.1

For information contact:

Jim Storey

Director, Investor Relations & Corporate Communications

704.973.7107

jstorey@horizonlines.com

HORIZON LINES’ STOCK TO TRADE ON THE OTC MARKET WITH NEW

TRADING SYMBOL HRZL STARTING OCTOBER 20, 2011

CHARLOTTE, NC, October 19, 2011 – Horizon Lines, Inc. (NYSE: HRZ), the nation’s leading domestic ocean shipping company, today announced that its common stock will begin trading on the OTCQB Marketplace, effective October 20, 2011.

OTC Markets Group Inc. operates the world’s largest electronic marketplace for broker-dealers to trade unlisted stocks, including the OTCQB Marketplace. Investors will be able to view the Real Time Level II stock quote, which provides detailed quote information by market maker, for Horizon Lines at http://www.otcmarkets.com under the ticker symbol HRZL.

The transition to the OTCQB Marketplace comes after the New York Stock Exchange (NYSE) announced that trading of the common stock of Horizon Lines will be suspended prior to the market opening on October 20, 2011. The stock is being suspended because it did not maintain an average market capitalization of at least $15 million over a consecutive 30-trading-day period, as required by NYSE continued listing standards.

Horizon Lines is appealing the NYSE’s determination. The company has been advised by the NYSE that additional action to pursue delisting of the stock will not be undertaken until the appeal is completed. In the meantime, the company’s stock will trade on the OTCQB Marketplace under the new HRZL stock symbol.

The transition to the OTCQB Marketplace does not change the company’s obligation to file periodic and other reports with the Securities and Exchange Commission under applicable federal securities laws. In addition, the transition of the company’s stock to the OTCQB Marketplace will have no effect on the shares themselves. Horizon Lines’ shareholders remain owners of the common stock and will be able to trade the stock on the OTCQB Marketplace as of October 20, 2011.

“Our stock’s change in trading venue does not have any impact on our ability to provide excellent service to our customers,” said Stephen H. Fraser, President and Chief Executive Officer. “We continue to move forward with a new financial structure resulting from our recent successful refinancing that provides adequate liquidity to fund continuing operations and affords us the opportunity to grow our business and reduce debt over time.”

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.

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: our ability to maintain adequate liquidity to operate our business; our ability to refinance, repay, or extend our indebtedness when it becomes due; volatility in fuel prices; the cyclical nature of international shipping industry and resulting volatile changes in freight rates; decreases in shipping volumes; failure to comply with the terms of our probation imposed by the court in connection with our plea relating to antitrust matters; any new adverse developments relating to antitrust matters in any of our trades; failure to resolve or successfully defend pending and future civil antitrust claims; government investigations related to environmental regulations including recordkeeping and reporting requirements for vessel generated pollution and any other government investigations and legal proceedings; 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; severe weather and natural disasters; the aging of our vessels and unexpected substantial dry-docking or repair costs for our vessels; the transfer of the listing of the company’s common stock from the NYSE to the OTCQB Marketplace; and the decreased liquidity for the company’s common stock.

Page 3 of 3

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.

# # #