Exhibit 99.1

PRESS RELEASE

For information contact:

Jim Storey

Director, Investor Relations & Corporate Communications

704.973.7107

jstorey@horizonlines.com

HORIZON LINES STOCKHOLDERS APPROVE 1-FOR-25 REVERSE STOCK

SPLIT AT SPECIAL STOCKHOLDER MEETING

CHARLOTTE, N.C. (December 8, 2011) – Horizon Lines, Inc. (OTCQB: HRZL) announced that stockholders at the company’s special stockholders meeting on December 2, 2011, voted to approve, among other things, a 1-for-25 reverse stock split.

Stockholders also approved the other three proposals presented at the special meeting. Stockholders approved amending the company’s certificate of incorporation to authorize the issuance of warrants in lieu of cash or redemption notes in consideration for “Excess Shares” to holders who cannot establish U.S. citizenship to facilitate compliance with the Jones Act. Stockholders also approved the company’s restated certificate of incorporation to combine into one document all of the provisions of the prior certificate of incorporation, the elimination of certain inapplicable provisions and the amendments approved by stockholders at the special stockholders meeting. Additionally, stockholders approved the company’s proposal to increase the authorized number of shares to 2.5 billion from 100.0 million; however, the share increase proposal would only have become effective if the reverse stock split had not been approved by stockholders.

Approximately 83.4% of the company’s 56.6 million shares eligible to vote were represented in the voting, which was open to stockholders of record as of October 7, 2011. With the proposals passed, the company on December 7, 2011, filed its restated certificate of incorporation to, among other things, effect the 1-for-25 reverse stock split. The reverse stock split reduces the number of shares of common stock outstanding to 2.3 million from 56.7 million.

“The reverse stock split is a strategically important step that will help the company meet minimum stock price listing standards that are required by the national stock exchanges,” said Stephen H. Fraser, Horizon Lines President and Chief Executive Officer. “The reverse split, when combined with our focus on executing the planned deleveraging of our existing indebtedness and successful execution of our business plan, should help Horizon attract quality investors and analysts over time.”

As previously disclosed, the company’s recapitalization plan announced in October allows, in certain circumstances, Horizon Lines to reduce outstanding debt by $49.7 million in

January by mandatorily converting a portion of the 6.00% convertible Series B notes for common stock or warrants at $18.25 per share (post split). Horizon Lines also has the opportunity to reduce debt by another $49.7 million in July 2012 by issuing equity or warrants at $18.25 per share (post split) through a mandatory conversion of the Series B notes, provided certain conditions are satisfied. Additionally, beginning October 5, 2012, the company has the right to convert, at its option, in whole or in part, into common stock or warrants approximately $178.8 million of 6.00% Series A convertible notes, provided that the 30-trading-day, volume-weighted average price of the common stock is at least $15.75 (post split) per share at the conversion date.

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. 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 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 antitrust claims; any other government investigations and 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.

# # #