Exhibit 99.1

PRESS RELEASE

For information contact:

Jim Storey

Director, Investor Relations & Corporate Communications

704.973.7107

jstorey@horizonlines.com

HORIZON LINES CLARIFIES EXCHANGE OFFER DOCUMENTS ON SEPTEMBER 26, 2011

CHARLOTTE, NC, September 26, 2011 – Horizon Lines, Inc. (NYSE: HRZ) announced that it filed on September 26, 2011, an amendment to its Registration Statement on Form S-4 and an amendment to Schedule TO relating to its previously announced exchange offer and consent solicitation for its $330.0 million of existing unsecured 4.25% convertible senior notes (“2012 convertible notes”). The exchange offer documents were revised in response to comments received by the Securities and Exchange Commission (SEC) to (i) further clarify what exchange consideration holders of the 2012 convertible notes who are non-U.S. citizens will receive and (ii) make other updating and conforming changes. The SEC is continuing to review the company’s Registration Statement on Form S-4 relating to the exchange offer and consent solicitation and has not yet declared the Registration Statement effective, which is a condition of the exchange offer, among others.

As part of the exchange offer, the company is also seeking consents from all holders of the 2012 convertible notes to remove substantially all of the restrictive covenants and certain events of default from the indenture governing the 2012 convertible notes.

The company and its advisors continue to work with the financial and legal advisors to the informal committee of noteholders to finalize the documentation and terms of the recapitalization plan, of which the exchange offer and consent solicitation are an integral part. The company intends to complete the exchange offer of the existing 2012 convertible notes by the end of September, at which time it expects to close the entire refinancing.

As discussed in the exchange offer documents, each participating holder in the exchange offer must state their U.S. citizenship by completing a questionnaire and certifying whether such holder is a U.S. citizen prior to the company accepting such holder’s tender and consent of its 2012 convertible notes in the exchange offer. Each holder must provide the DTC Account Number of its custodian, the principal amount of notes tendered and the VOI number that relates to its tendering instructions. A holder can obtain the VOI number from its custodian. The

Horizon Lines Clarifies Exchange Offer Documents

completed questionnaire and any additional information, correspondence or requests for reconsideration of citizenship determination may be sent to the attention of Michael F. Zendan II, Senior Vice President, General Counsel and Secretary of Horizon Lines, Inc., who may be contacted by telephone at 704-973-7029, by fax at 704-973-7010, or by e-mail at MZendan@HorizonLines.com. The information and exchange agent for the exchange offer and consent solicitation is Global Bondholder Services Corporation.

Important Information about the Exchange Offer

This release is for informational purposes only and is not an offer to buy or the solicitation of an offer to sell any security. An exchange offer will only be made by means of a prospectus, a letter of transmittal and other offer documents, as described below. In connection with the exchange offer by Horizon Lines, Inc., the company previously filed a Registration Statement on Form S-4 (which contains a preliminary prospectus), amendments to the Registration Statement, an exchange offer statement on Schedule TO, as amended, and other related documents and materials with the SEC. Investors and security holders are strongly urged to carefully review the registration statement, amendments to the registration statement, the preliminary prospectus, the exchange offer statement, the amendments to the exchange offer statement and the other related documents and materials filed with the SEC, including the final prospectus described below, when available, as well as any amendments and supplements thereto because they will contain important information about the company, the exchange offer and related transactions and are the sole means by which any offer to exchange or sell, or any solicitation of any such offers, will be made.

The registration statement contains a preliminary prospectus and related transmittal materials that have been delivered to holders of the 4.25% convertible senior notes. Investors and security holders may obtain a free copy of the registration statement, amendments to the registration statement, preliminary prospectus and transmittal materials, as well as other documents filed by the company with the SEC, at the SEC’s website, www.sec.gov. Prior to the completion of the exchange offer, the registration statement must become effective under the securities laws, and after effectiveness, the company will file with the SEC the final prospectus. Investors and security holders are strongly urged to carefully review the final prospectus when it is available. Copies of the exchange offer documents, the U.S. citizenship questionnaire and other filed documents will be available for free at the company’s website, www.horizonlines.com, or by making a request to Horizon Lines, Inc., 4064 Colony Road, Suite 200, Charlotte, North Carolina 28211, (704) 973-7000, Attention: Jim Storey, Director, Investor Relations & Corporate Communications.

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

Horizon Lines Clarifies Exchange Offer Documents

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, and trades on the New York Stock Exchange under the ticker symbol HRZ.

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 ability of the parties to agree on the final terms of the refinancing; our ability to close on the refinancing; our ability to satisfy other conditions of the refinancing, including satisfaction of any remaining diligence requests; the ability of the investors to fund the refinancing; general conditions in the capital markets; general economic conditions; our ability to maintain adequate liquidity to operate our business; volatility in fuel prices and in freight rates; decreases in shipping volumes; our ability to remain Jones Act compliant because of changes in ownership; or our ability to continue as a going concern.

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.

# # #