Exhibit 99.1

PRESS RELEASE

For information contact:

Jim Storey

Director, Investor Relations & Corporate Communications

704.973.7107

jstorey@horizonlines.com

HORIZON LINES REPORTS SECOND-QUARTER FINANCIAL RESULTS

Quarter Negatively Impacted by China Service, High Fuel Prices

Debt Refinancing Definitive Transaction Expected in August

CHARLOTTE, NC, July 29, 2011 – Horizon Lines, Inc. (NYSE: HRZ) today reported financial results for the fiscal second quarter ended June 26, 2011.

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

On a GAAP basis, the second-quarter net loss from continuing operations totaled $7.0 million, or $0.22 per diluted share, on revenue from continuing operations of $307.5 million. On an adjusted basis, the company recorded a second-quarter net loss from continuing operations of $20.9 million, or $0.67 per diluted share, after adjustments totaling a negative $13.9 million, or $0.45 a share. The adjusted net loss excludes the net reversal of $18.2 million related to legal settlements. The amounts include $19.2 million from the reversal of the $30.0 million charge recorded in the fourth quarter of fiscal 2010 for the company’s antitrust settlement with the U.S. Department of Justice. As previously

disclosed, the company originally agreed to a fine of $45.0 million, payable over five years without interest, to resolve the DOJ’s antitrust investigation related to domestic ocean shipping. That fine was reduced to $15.0 million in April, and the $19.2 million reversal represents the change in present value of the fine. The net legal settlement exclusion is partially offset by $4.8 million in charges related to an impairment on cranes held for sale that were originally destined for Alaska, antitrust-related legal expenses, refinancing costs, employee severance, and the associated tax impact of $0.5 million (see the reconciliation tables for specific line-item amounts).

In the year-ago second quarter, Horizon Lines reported net income from continuing operations of $4.1 million, or $0.14 per diluted share, on revenue of $291.4 million. On an adjusted basis, net income from continuing operations totaled $5.2 million, or $0.17 per diluted share, after excluding antitrust-related legal expenses and costs for early retirement of certain union employees totaling $1.1 million, or $0.03 per share.

Container volume for the 2011 second quarter totaled 75,208 loads, a 16.4% increase from 64,596 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, volume totaled 61,315 loads, a decrease of 2,908 loads, or 4.5%, from 64,223 loads a year ago. Relative to the 2010 second quarter, volumes were up in Alaska and Guam, and down in Puerto Rico and Hawaii.

Container rates, net of fuel, for the 2011 second quarter fell 7.9% to $2,989 from $3,246 a year ago. The reduction was due to the addition of China volume, with lower average and declining rates, and the continued pricing pressures in Puerto Rico. Excluding China, container rates, net of fuel, rose 0.7% to $3,278 in the second quarter from a year ago.

The company’s vessels delivered 83% on-time performance, measured to the minute, in the second 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 and port congestion in Asia, as well as extra mileage required to avoid the radioactive plume resulting from the nuclear plant incident in Fukushima, Japan. Combined on-time performance for Alaska, Hawaii and Puerto Rico was 91%.

Vessel utilization was 59% during the quarter, compared with 60% in 2010, while vessel availability remained near 100%, driven by the company’s comprehensive fleet maintenance program.

“Soft container rates in the trans-Pacific market and high fuel prices pushed our second-quarter financial performance significantly below last year’s,” said Stephen H. Fraser, President and Chief Executive Officer. “Trans-Pacific rates remained under pressure throughout most of the quarter, as some large international carriers continued to take aggressive rate actions amid capacity expansion in the tradelane. This excess capacity pressured overall volumes in June, resulting in further deterioration of spot rates and the postponement of peak-season surcharges. In addition, average fuel costs during the quarter were up 41% from a year ago.

“The start-up of a new trans-Pacific service has coincided with one of the most challenging periods in the history of the tradelane,” Mr. Fraser said. “The revenue shortfalls and costs associated with this service negatively impacted adjusted EBITDA by approximately $16.0 million in the second quarter, or by $10.6 million when compared against the previous year’s performance under the Maersk agreements, which ended in December.

“Looking at our traditional domestic ocean shipping business, Alaska and Hawaii continued to demonstrate operating profitability during the second quarter, although higher fuel costs and volume declines in Puerto Rico and Hawaii negatively impacted results relative to a year ago,” Mr. Fraser said. “Rate pressures also persisted in Puerto Rico, due largely to overcapacity in the tradelane. In contrast, our operation in Alaska operated at near-full capacity utilization during the quarter and also continued to generate strong third-party terminal services revenue.

“During the quarter, we continued to focus on cost management and efficient customer service,” Mr. Fraser added. “We worked to preserve liquidity by significantly reducing operating costs, and we are continuing to move towards a comprehensive restructuring of our existing debt.”

Second-Quarter 2011 Financial Highlights

Operating Revenue – Second-quarter operating revenue from continuing operations increased 5.5% to $307.5 million from $291.4 million a year ago. Fuel surcharges accounted for approximately 20.7% of total revenue in the 2011 second quarter, and 15.0% of total revenue in the year-ago quarter. The largest factors in the $16.1 million revenue improvement were: a $29.3 million increase in revenue from the new China

Operating Income – GAAP operating income from continuing operations for the second quarter totaled $4.3 million, compared with $14.0 million a year ago. The GAAP operating income includes the $18.2 million net reversal related to legal settlements and $4.8 million in charges related to equipment impairment, antitrust-related legal expenses, refinancing costs, and employee severance (see reconciliation tables for specific line-item amounts). The 2010 second-quarter GAAP operating income includes $1.0 million in antitrust-related legal expenses and $0.1 million in costs for union employee severance. Adjusting for these items, the second-quarter 2011 adjusted operating loss from continuing operations totaled $9.1 million, compared with adjusted operating income from continuing operations of $15.1 million a year ago. Second-quarter 2011 operating results were negatively impacted by the termination of various Maersk agreements, lower fuel recovery, reduced domestic container volumes and lower rates. These negative factors were partially offset by vessel labor and lease savings, inland rail and trucking savings, and strong non-transportation/terminal services revenue.

EBITDA – EBITDA from continuing operations totaled $19.7million for the 2011 second quarter, compared with $28.3 million for the same period a year ago. Adjusted EBITDA from continuing operations for the second quarter of 2011 was $6.3 million, compared with $29.4 million for 2010. EBITDA and adjusted EBITDA for the 2011 and 2010 second quarters were impacted by the same factors affecting operating income, as noted in the table below:

*Termination of Maersk agreements includes loss of TP1 trans-Pacific fixed-income stream, terminal services, and additional expenses associated with stevedoring and containers.

Shares Outstanding – The company had a weighted daily average of 31.0 million fully diluted shares outstanding for the second quarter of 2011, compared with 30.9 million a year ago.

Six-Month Results – For the six months ended June 26, 2011, operating revenue from continuing operations increased 4.8% to $592.9 million from $566.0 million for the same period in 2010. EBITDA from continuing operations totaled $12.3 million compared with $40.4 million a year ago. Adjusted EBITDA for the first six months of 2011 totaled $4.5 million, after excluding the $18.2 million net reversal related to legal settlements and $10.4 million in antitrust-related legal expenses, impairment charges, refinancing costs and severance-related charges (see reconciliation tables for specific line-item amounts). Adjusted EBITDA for the first six months of 2010 totaled $42.7 million, after excluding charges related to antitrust-related legal expenses and severance-related charges totaling $2.3 million. The net loss from continuing operations for the 2011 six-month period totaled $40.3 million, or $1.30 per share, compared with a net loss from continuing operations of $7.6 million, or $0.24 per share, for the same period a year earlier. The adjusted net loss from continuing operations for the first six months of 2011 totaled $48.6 million, or $1.57 per share, compared with an adjusted net loss from continuing operations of $5.2 million, or $0.17 per share, a year ago.

Liquidity, Credit Facility Compliance & Debt Structure – As of June 26, 2011, the company had total liquidity of $21.3 million, consisting of $3.4 million in cash and $17.9 million of revolver availability. The company’s trailing 12-month interest coverage and senior secured leverage ratios were 1.88 times and 5.17 times, respectively, in compliance with the amended credit agreement requirement for the second quarter of above 1.5 times and below 6.25 times, respectively. Funded debt outstanding totaled

$611.3 million, compared with $585.3 million at the end of the first quarter, and $563.1 million a year ago. The funded debt outstanding at June 26, 2011, consisted of $272.9 million in senior secured debt, $330.0 million in convertible notes, and $8.4 million of capital lease obligations, at a weighted average interest rate of 5.63%.

The company’s senior secured debt matures in August 2012, but the maturity will accelerate to February 2012 if the convertible notes are not refinanced or if arrangements are not made for their refinancing by that date. The company expects to experience a covenant breach under the senior credit facility in connection with the amended financial covenants upon the close of the third quarter of 2011, when covenant ratios tighten to above 2.75 times for interest coverage and below 3.0 times for senior secured leverage. The company anticipates that it will be refinanced prior to any possible covenant noncompliance, or will work with its lenders and their advisors to obtain waivers and amendments.

Please see attached schedules for the reconciliation of second-quarter and first-half 2011 and 2010 reported GAAP results and Non-GAAP adjusted results.

Second-Quarter Tradelane Review

Second-quarter volume in Alaska improved from a year ago, and business conditions strengthened from the first-quarter due to seasonality and the state’s improving economy. The company’s Alaska business continued to benefit from third-party terminal services operations, and also experienced growth in seafood, groceries and refrigerated commodities, as well as household goods. The company expects volumes to remain strong through the third quarter.

In Hawaii, second-quarter volume contracted from a year ago, as the business environment remained challenging due to the state’s slow and uneven economic recovery. A gradual recovery in tourism is expected to slowly add jobs, although overall construction remains flat and the state government continues to operate under fiscal constraints. The company believes the steady military sector and the gradual economic recovery will help stabilize volumes as the year progresses.

Second-quarter volume in Puerto Rico declined from a year ago, due to the island’s continuing recession and ongoing overcapacity. However, the company expects volume to improve in the second half of the year, due in part to the recent decision by a competitor to suspend vessel service from the Northeast.

The company’s new China service experienced a very challenging second quarter due to general market rate softness and high fuel prices. The company expects to operate at near-full capacity through the third quarter, but at significantly lower-than-anticipated container rates. The overcapacity situation has caused some carriers to pull out of the market or postpone seasonal sailings, which might help stabilize rates.

In Guam, the company’s second-quarter volume increased from a year ago, due to service and schedule improvements combined with some growth in construction project business. While overall tradelane volume remains stable, the company expects its second-half volumes to improve from year-earlier levels, due largely to service improvements and construction projects. Additional new construction projects associated with the military buildup are expected to be placed on hold until the U.S. and Japan agree to a new timeline for the military relocation from Okinawa to Guam. In late June, the two countries agreed to delay the move beyond 2014, increasing the likelihood that spending associated with the Guam buildup will be gradual and spread over numerous years.

Outlook & Refinancing Update

While challenges remain in the second half of 2011, the company is somewhat encouraged by developments in its domestic ocean business. Volume and business trends in Alaska remain strong, and Hawaii volumes are showing signs of stabilization, as the state’s economy continues to slowly improve. Puerto Rico remains in a multi-year recession, but volumes and prices could begin to stabilize, partly as a result of a competitor’s recent decision suspend vessel operations from the port of Philadelphia.

The company’s new trans-Pacific express service to China remains significantly challenged by the depressed rate environment and high fuel prices, despite good customer support and the recent departure of some new carriers serving the tradelane.

“Financially, we anticipate that our China service will continue to operate at a sizeable loss in absolute terms and at a significant deficit relative to the revenue and operating profit generated by the previous Maersk business,” Mr. Fraser said. “However, the rate of loss should begin to improve in the third quarter. Overall, we expect adjusted EBITDA to improve in the second half from the same period a year ago, as a result of stabilizing fuel prices and more secure conditions in our Jones Act markets. Due to the second-quarter shortfall, we now expect full-year adjusted EBITDA will be below our previous projections.”

Regarding the company’s refinancing, Horizon Lines and the majority of the holders of its 4.25% convertible senior notes continue to make significant progress in negotiations concerning certain substantive modifications to the recapitalization transaction announced on June 1, 2011, and the parties anticipate completing such negotiations and announcing a definitive transaction in the next several weeks. There is no assurance that negotiations will be successful.

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, 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. 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: our ability to maintain adequate liquidity to operate our business; our ability to repay our indebtedness; volatility in fuel prices and in freight rates; decreases in shipping volumes; 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. We undertake no obligation, and specifically decline any obligation, to publicly update or revise any forward-looking statement, whether as a result of new information, future events or otherwise. 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.

(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, (ii) the senior credit facility contains covenants that require the Company to maintain certain interest expense coverage and leverage ratios, w hich contain EBITDA, and (iii) 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 and w hen determining the payment of discretionary bonuses.

Horizon Lines, Inc.

June YTD Free Cash Flow

($ in millions)