Exhibit 99.1

PRESS RELEASE

For information contact:

Jim Storey

Director, Investor Relations & Corporate Communications

704.973.7107

jstorey@horizonlines.com

HORIZON LINES COMPLETES MANDATORY DEBT CONVERSION

$49.7 Million of 6.00% Series B Mandatorily Convertible Senior Secured

Notes Exchanged for Common Stock and Warrants

CHARLOTTE, NC, January 11, 2012 – Horizon Lines, Inc. today announced that it has completed the mandatory debt-to-equity conversion of approximately $49.7 million of the company’s 6.00% Series B Mandatorily Convertible Senior Secured Notes (the “Series B Notes”). The mandatory conversion reduces debt, lowers annualized interest payments and is expected to increase the value of the company’s shares outstanding.

Under the terms of the company’s recapitalization plan that was undertaken in October 2011, the Series B Notes are mandatorily convertible into shares of common stock or warrants in two equal installments on the three-month and nine-month anniversaries of their issuance, subject to certain conditions.

In accordance with these terms, on January 10, 2012, the company mandatorily converted approximately $49.7 million of the Series B Notes at a conversion rate of 54.7196 shares of common stock (reflecting the 1-for-25 reverse stock split of the company’s common stock effective December 7, 2011) per $1,000 principal amount of Series B Notes. Approximately $18.5 million of the Series B Notes were converted into 1,014,839 shares of common stock with the remainder being converted into warrants exercisable into shares of common stock. The distribution of common stock and warrants was based upon the U.S. citizenship verifications of the holders of the Series B Notes. Foreign holders, or holders who did not provide proof of U.S. citizenship, received warrants exercisable by U.S. citizens into an applicable quantity of common stock. All fractional interests were paid in cash.

“This mandatory conversion reduces the company’s annualized interest payments by approximately $3.0 million and represents a major step in deleveraging the company’s balance sheet under the opportunities provided by our new capital structure,” said Stephen H. Fraser, President and Chief Executive Officer. “Affording us the ability to decrease debt is an essential component of the refinancing structure that we put in place last October with the help of our note holders. Issuing stock as a means to replace debt also allows us to immediately increase the total market value of our equity, as well as build shareholder value over time.”

Subject to certain conditions, the remaining approximately $49.7 million in aggregate principal amount of the Series B Notes is scheduled to be mandatorily converted into shares of common stock and warrants in July 2012. The Series B Notes will be automatically converted into 6.00% Series A Convertible Senior Secured Notes due 2017 on October 5, 2012 if the company is unable to effect mandatory conversion before then.

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., based in Charlotte, NC, is listed on the New York Stock Exchange and trades on the OTCQB 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. 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, “anticipate,” “will,” “may,” “expect,” “would,” “could,” 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: failure to remain listed on the NYSE; our ability to sub-charter certain of our leased vessels, 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 any government investigations related to (i) environmental regulations including recordkeeping and reporting requirements for vessel generated pollution, (ii) the imposition of fuel surcharges in connection with government contracts, or (iii) any other matters and related legal proceedings; suspension or debarment by the federal government; volatility in fuel prices; or decreases in shipping volumes.

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-Q filed with the SEC on November 4, 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.

# # #