PRESS RELEASE

For information contact:

Jim Storey

Director, Investor Relations & Corporate Communications

704.973.7107

jstorey@horizonlines.com

HORIZON LINES ADOPTS SHAREHOLDER RIGHTS PLAN TO PROTECT

NET OPERATING LOSS CARRYFORWARDS

CHARLOTTE, NC, August 28, 2012 – Horizon Lines, Inc. (OTCQB: HRZL) today announced that its Board of Directors has adopted a shareholder rights plan (the “Rights Plan”) designed to preserve the value of its significant net operating loss carryforwards (“NOLs”) and other related tax assets under Section 382 of the Internal Revenue Code (the “Code”).

The Company’s ability to utilize these tax assets would be substantially limited upon an “ownership change,” which is generally defined in Section 382 of the Code as a more than 50 percentage point increase in stock ownership, during a rolling three-year testing period, by “5% shareholders” (as defined in Section 382 of the Code). The Rights Plan was adopted to reduce the likelihood of this occurring by deterring the acquisition of Company stock, or securities that are exercisable for or convertible into Company stock, by persons or groups that would create such “5% shareholders.” The Company’s estimated NOLs for United States federal income tax purposes as of December 5, 2011 were approximately $117.4 million.

“The Company has a significant asset in its NOLs and the Board took this prudent step to protect this asset,” said Jeffrey A. Brodsky, Chairman of the Board of Directors.

Under the Rights Plan, one right will attach to each share of common stock of Horizon Lines. Pursuant to the Rights Plan, if any person or group (subject to customary exceptions specified in the Rights Plan) acquires “beneficial ownership” (as defined in the Rights Plan) of 4.9% or more of the “outstanding shares” of the Company’s common stock without the Board’s approval, significant dilution in the economic interest and voting power of such person or group would occur. For purposes of calculating percentage ownership under the Rights Plan, “outstanding shares” of the Company’s common stock will include all of the shares of common stock actually issued and outstanding, as well as all of the shares of common stock issuable upon the exercise of all outstanding warrants (whether or not such warrants are currently exercisable). The Rights Plan also provides that a person or group will be deemed to “beneficially own” all of the shares of the Company’s common stock that such person or group would have the right to acquire (including through the acquisition of warrants) if it had been a “U.S. Citizen” (as defined in the Company’s certificate of incorporation). Existing shareholders who currently beneficially own 4.9% or more of the “outstanding shares” of common stock will cause this dilutive event to occur only if they acquire

beneficial ownership of additional stock of the Company (including through the acquisition of warrants) in an amount in excess of 0.5% of the “outstanding shares” of common stock. In its discretion, the Board may exempt certain transactions from the provisions of the Rights Plan, including if it determines that the transaction will not jeopardize the deferred tax assets or the transaction will otherwise serve the Company’s best interests. The Rights Plan may be terminated by the Board of Directors of Horizon Lines at any time prior to the rights becoming exercisable.

The rights are not exercisable until a later date and will expire on August 27, 2015, or earlier upon the date that: (1) the Board determines that the plan is no longer needed to preserve the deferred tax assets or is no longer in the best interest of the Company and its stockholders, (2) the Board determines, at the beginning of a specified period, that no tax benefits may be carried forward, or (3) the rights are redeemed or exchanged by the Board pursuant to the Rights Plan. The issuance of the rights is not a taxable event and will not affect the Company’s reported financial condition or results of operations (including earnings per share).

Horizon Lines will file additional information about the terms and conditions of the Rights Plan with the Securities and Exchange Commission.

In connection with the adoption of the Rights Plan, Horizon Lines today announced that its Board of Directors has amended the Company’s bylaws to require any person or group who acquires beneficial ownership of 4.9% or more of the “outstanding shares” of the Company’s common stock, taking into account all of the shares of the Company’s common stock that such person or group would have the right to acquire (including through the exercise of warrants) if it had been a “U.S. Citizen” (as defined in the Company’s certificate of incorporation), to notify the Company of its ownership and provide certain additional information. These amendments are designed to enhance the Company’s ability to monitor beneficial ownership levels under the Rights Plan.

About Horizon Lines

Horizon Lines, Inc. is one of the nation’s leading domestic ocean shipping companies and the only ocean cargo carrier serving all three noncontiguous domestic markets of Alaska, Hawaii and Puerto Rico from the continental United States. The company maintains a fleet of 15 fully Jones Act qualified vessels and operates five port terminals in Alaska, Hawaii and Puerto Rico. A trusted partner for many of the nation’s leading retailers, manufacturers and U.S. government agencies, Horizon Lines provides reliable transportation services that leverage its unique combination of ocean transportation and inland distribution capabilities to deliver goods that are vital to the prosperity of the markets it serves. The company is based in Charlotte, NC, and its stock trades on the over-the-counter market under the 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: the difficulty of determining all of the facts relevant to Section 382 of the Code; unreported buying and selling activity by securityholders; unanticipated interpretations of the Code and related regulations; and the adoption of the Rights Plan may not prevent one or more securityholders of the Company from, notwithstanding the dilution to such securityholder’s interests under the Rights Plan, engaging in buying and selling activity that may have an adverse impact on the Company’s tax attributes.

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 April 10, 2012, 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.

# # #