Exhibit 99.1

PRESS RELEASE

For information contact:

Jim Storey

Director, Investor Relations & Corporate Communications

704.973.7107

jstorey@horizonlines.com

HORIZON LINES REPORTS THIRD-QUARTER FINANCIAL RESULTS

Quarter Negatively Impacted by Goodwill Impairment Charge,

FSX Losses, Volume and Rate Pressures

CHARLOTTE, NC, November 7, 2011 – Horizon Lines, Inc. (OTCQB: HRZL) today reported financial results for the fiscal third quarter ended September 25, 2011.

Financial results are being presented on a continuing operations basis, excluding discontinued logistics operations.

Comparison of GAAP and Non-GAAP Results from Continuing Operations

On a GAAP basis, the third-quarter net loss from continuing operations totaled $126.5 million, or $4.09 per diluted share, on revenue from continuing operations of $321.9 million. On an adjusted basis, the company recorded a third-quarter net loss from continuing operations of $5.6 million, or $0.18 per diluted share, after excluding charges totaling $120.9 million, after tax, or $3.91 per share. The pre-tax charges include a $117.5 million goodwill impairment charge, as well as a $2.2 million impairment of our Guam cranes, which have been classified as held for sale. The pre-tax charges also include $0.7 million for antitrust-related legal fees, $0.3 million of non-cash interest accretion related to a legal settlement, $0.1 million for employee severance, and a tax expense impact of $0.1 million.

Certain qualitative and quantitative factors, including a deterioration in earnings and the expected shutdown of the FSX service, indicated that the company may have goodwill impairment. Although the Company has not yet completed its analysis due to the complexities involved in determining the implied fair value of goodwill, it has concluded that an impairment loss is probable and can be reasonably estimated. The pre-tax $117.5 million goodwill impairment charge represents the company’s best estimate at this time. The Company’s estimated $117.5 million impairment charge is due to the reduction in projected earnings as well as an appreciation in the fair value of certain long term assets above book value. The final amount of the impairment charge will be determined in the fourth quarter of 2011 and may require an adjustment to the estimated amount, which may be material.

In 2010, Horizon Lines reported third-quarter net income from continuing operations of $8.2 million, or $0.26 per diluted share, on revenue of $297.6 million. On an adjusted basis, net income from continuing operations totaled $11.4 million, or $0.37 per diluted share, after excluding impairment charges, antitrust-related legal expenses, costs for early retirement of certain union employees, and tax adjustments totaling $3.2 million, or $0.11 per share.

Container volume for the 2011 third quarter totaled 80,155 loads, a 22.0% increase from 65,726 loads for the same period a year ago. The volume growth was due to the company’s new China service, which began operating in December 2010. Excluding China revenue loads in the third quarters of 2011 and 2010, 2011 volume totaled 62,882 loads, a decrease of 2,294 loads, or 3.5%, from 65,176 loads a year ago. Relative to the 2010 third quarter, volumes were up in Guam, and down in Alaska, Hawaii and Puerto Rico.

Container rates, net of fuel, for the 2011 third quarter fell 12.4% to $2,843 from $3,247 a year ago. The reduction was due to the addition of volume in the company’s China service, with lower average rates, and continuing pricing pressures in Puerto Rico. Excluding China, container rates, net of fuel, rose 0.4% to $3,267 in the third quarter from a year ago.

Volume, Rates and Fuel

The company’s vessels delivered 83% on-time performance, measured to the minute, in the third quarter, 10 percentage points below the 93% on-time performance recorded in the same quarter a year ago. The decline was mostly due to delays in the trans-Pacific service related to fog, port congestion and typhoon activity in Asia, as well as hurricane avoidance in the Puerto Rico tradelane. Combined on-time performance, measured to the minute, for Alaska, Hawaii and Puerto Rico was 87%.

Vessel utilization was 61% during the quarter, compared with 58% in 2010, due largely to an increase in westbound China volumes. Vessel availability remained near 100%, a result of the company’s comprehensive fleet maintenance program.

“The third quarter was adversely impacted by continued and growing losses in our trans-Pacific service, and to a much lesser extent by lower volumes in our domestic tradelanes and continued rate pressure in Puerto Rico,” said Stephen H. Fraser, President and Chief Executive Officer. “Additionally, our results were hurt by the loss of steady revenue from our previous trans-Pacific agreement and the expiration of certain equipment sharing agreements with Maersk that were in place during the year-ago quarter.

“Our trans-Pacific service operated at a much wider-than-anticipated loss, resulting from falling container rates and our inability to adequately recover fuel cost increases,” Mr. Fraser continued. “While the service has been successful in meeting most of its operating and volume objectives, its financial performance has been severely pressured by the tradelane’s persistent rate weakness, evidenced by the more than 37% decline in eastbound freight rates over the past 12 months, and by the more than 40% rise in fuel prices since we launched the service in December 2010.”

In the fourth quarter, Horizon Lines announced on October 24, 2011, that it is discontinuing its trans-Pacific service due to the expected continuation of a weak and volatile trans-Pacific rate environment, high fuel prices and the resulting outlook for continued large operating losses. The company will cease all operations related to the service during the fourth quarter and classify it as a discontinued operation. As a result of the shutdown, the company expects to record a pretax restructuring charge of approximately $105 million to $110 million in its fiscal fourth quarter of 2011. The estimated charge includes costs for: vessel lease expense, net of estimated sublease income; the return of excess rolling stock equipment; severance and facility expenses.

Regarding the company’s outlook, economic conditions remain challenging in the fourth quarter across all of the company’s markets. However, the company is well positioned in its markets and operating under a new debt structure, and will soon be solely focused on its core domestic ocean shipping business.

“With our refinancing completed in early October, we now have in place a new, long-term capital structure that removes the refinancing risk related to the maturity of our previous debt,” Mr. Fraser said. “And with our decision to terminate our trans-Pacific service, we have also moved decisively to limit the losses caused by the volatile rate environment and high fuel prices. Together, these actions position us on solid financial footing, with

adequate liquidity to fund our continuing core domestic operations and the shutdown of our China/Guam service, as well as provide us with the opportunity to deliver a more predictable financial performance in the future.”

Third-Quarter 2011 Financial Highlights

Operating Revenue Change (in millions)

Adjusted EBITDA Change (in thousands)

Liquidity, Credit Facility Compliance & Debt Structure

On October 5, 2011, the company completed a comprehensive refinancing of its entire capital structure, resulting in the reclassification of the company’s debt to “long-term” from “current” and substantially reducing the likelihood of any potential covenant defaults. Earlier in the year, the company received a “going-concern” audit opinion that was included in its form 10-K annual report, due to the company’s projected covenant defaults throughout 2011. As a result of the “going-concern” audit opinion, the company’s debt was classified as current in the balance sheets through the second quarter.

The funded debt component of Horizon Lines’ new capital structure includes $225 million of 11.00% first-lien secured notes due October 15, 2016; $100 million of second-lien secured notes maturing October 15, 2016 and bearing interest at 13.00% if paid in cash, 14.00% if paid 50% in cash and 50% in kind, and 15.00% if paid in kind (with additional second-lien secured notes); and $278.1 million of 6.0% convertible secured notes due April 15, 2017. Also remaining outstanding are $2.2 million of 4.25% convertible notes due August 15, 2012 and a $7.8 million capital lease. Currently, the company’s weighted average interest rate for funded debt is 9.02%, assuming cash payment on the second-lien notes.

A new asset-based loan (ABL) revolving credit facility provides liquidity for continuing operations. Availability under the ABL facility is based on a percentage of eligible accounts receivable and customary reserves, with a maximum of $100 million. The ABL facility matures in October 2016 and bears interest at LIBOR or a base rate, plus a spread determined by a combination of revolver availability and a defined leverage ratio.

Currently, Horizon Lines is operating with ample ABL revolver availability. Letters of credit issued against the ABL facility total $19.3 million, but there are no outstanding borrowings. Total unused borrowing capacity is $59.1 million.

Please see attached schedules for the reconciliation of third-quarter and nine-month 2011 and 2010 reported GAAP results and Non-GAAP adjusted results.

Third-Quarter Tradelane Review

“In our traditional domestic ocean shipping business, reduced container volumes in each of our tradelanes relative to last year reflect the overall soft business climate that we have experienced in our markets,” Mr. Fraser said. “Alaska continued to benefit from a stable economy and solid third-party terminal services revenue. Hawaii exhibited sporadic growth led by tourism, while volume and rate pressures persisted in Puerto Rico, due largely to the ongoing multi-year recession there.

“Overall, consumers remain very cautious across all of our markets, due to the still uncertain macroeconomic environment,” Mr. Fraser continued. “As a result, we are continuing to focus on cost management and liquidity preservation efforts. These efforts include reducing operating costs, pursuing the sale of selected assets, and seeking contract concessions where practical.”

Third-quarter volume in Alaska declined slightly from a year ago, partly due to lower-than-anticipated seafood volumes and the closing of a major home improvement store in Kenai. The company’s Alaska business continued to benefit from third-party terminal services operations in the quarter. The state economy remains stable, and each Alaska citizen received $1,174 in October from this year’s permanent dividend fund payout. The company expects the business climate and volumes to remain stable through the fourth quarter.

In Hawaii, third-quarter volume contracted somewhat from a year ago, as the business environment remained challenged by the state’s slow economic recovery. A gradual recovery in tourism is expected to slowly add jobs, although overall construction remains flat and the state government continues to face fiscal challenges. The company is focusing on operational improvements and service reliability and believes the steady military sector and business from new, recently secured customers will help stabilize future volumes, although it expects overall consumer spending to remain constrained.

Third-quarter volume in Puerto Rico also declined from a year ago, due largely to the island’s continuing recession, high unemployment and ongoing overcapacity of carriers serving the market. These factors also pressured container rates during the quarter. Despite the challenges, including an active hurricane season, the company remains focused on providing timely service and competitive routes. Horizon Lines is the only carrier serving Puerto Rico from all three ports in Houston, Texas, Jacksonville, Florida, and Elizabeth, New Jersey.

The company’s FSX service, which includes Guam and China, continued to face significant challenges in the form of persistent rate softness, high fuel prices and lack of business and economic growth in Guam. Although the FSX operated at 85% capacity utilization in the third quarter, rates remained significantly below expectations, and the company was unable to sufficiently recover fuel costs. In Guam, volumes increased from a year ago, partly due to service enhancements and improved market share, but the military move from Okinawa to Guam remains delayed, which in turn has caused related construction projects to be placed on hold.

NYSE Suspension of Trading

Due to the recent decline in the company’s market capitalization, the New York Stock Exchange (NYSE) suspended trading of the company’s common stock, effective prior to the opening of trading on October 20, 2011. At that time, the company’s stock began trading on the over-the-counter (OTC) market under a new stock symbol, HRZL. The company is appealing the NYSE’s action. During the appeal process, its common stock will remain listed on the NYSE, but trade on the OTC. A delisting of the company’s common stock is not considered an event of default under the terms of either its previous convertible notes or new convertible notes issued in the refinancing. However, should the NYSE decide to delist the company’s common stock at the conclusion of the appeal process, all of the company’s new convertible notes outstanding at such time will not be eligible for automatic conversion into common stock. Thereafter, the company will also be unable to exercise its conversion rights related to the new convertible notes until the company’s common stock is listed on a national exchange.

Use of Non-GAAP Measures

Horizon Lines reports its financial results in accordance with U.S. generally accepted accounting principles (GAAP). The company also believes that the presentation of certain non-GAAP measures, i.e., EBITDA, free cash flow and results excluding certain costs and expenses, provides useful information for the understanding of its ongoing operations and enables investors to focus on period-over-period operating performance without the impact of significant special items. The company further feels these non-GAAP measures enhance the user’s overall understanding of the company’s current financial performance relative to past performance and provide a better baseline for modeling future earnings expectations. Non-GAAP measures are reconciled in the financial tables accompanying this news release. The company cautions that non-GAAP measures should be considered in addition to, but not as a substitute for, the company’s reported GAAP results.

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: volatility in fuel prices; 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 antitrust claims; government investigations related to environmental regulations including recordkeeping and reporting requirements for vessel-generated pollution; government investigations relating to the imposition of fuel

surcharges in connection with government contracts; 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; catastrophic losses and other liabilities; the arrest of our vessels by maritime claimants; severe weather and natural disasters, or; the aging of our vessels and unexpected substantial dry-docking or repair costs for our vessels.

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.

(Tables Follow)

Horizon Lines, Inc.

Unaudited Condensed Consolidated Balance Sheets

(in thousands, except per share data)

Horizon Lines, Inc.

Unaudited Condensed Consolidated Statements of Operations

(in thousands, except per share data)

Horizon Lines, Inc.

Unaudited Condensed Consolidated Statements of Cash Flows

(in thousands)

Horizon Lines, Inc.

Adjusted Operating (Loss) Income Reconciliation

($ in Thousands)

Horizon Lines, Inc.

Adjusted Net (Loss) Income Reconciliation

($ in Thousands)

Horizon Lines, Inc.

Adjusted Net (Loss) Income Per Share Reconciliation

Horizon Lines, Inc.

EBITDA and Adjusted EBITDA Reconciliation

($ in Thousands)

Note: EBITDA is defined as net income plus net interest expense, income taxes, depreciation and amortization. We believe that EBITDA is a meaningful measure for investors as (i) EBITDA is a component of the measure used by our board of directors and management team to evaluate our operating performance, and (ii) EBITDA is a measure used by our management team to make day-to-day operating decisions. Adjusted EBITDA excludes certain charges in order to evaluate our operating performance, for making day-to-day operating decisions.

Horizon Lines, Inc.

September YTD Free Cash Flow

($ in millions)