Exhibit 99.1

PRESS RELEASE

For information contact:

Mike Avara

704-973-7027

mavara@horizonlines.com

HORIZON LINES REPORTS SECOND-QUARTER FINANCIAL RESULTS

Adjusted EBITDA Increases 92.1% and Rate, Net of Fuel, Rises 2.6% from Year Ago

CHARLOTTE, NC, August 2, 2013 – Horizon Lines, Inc. (OTCQB: HRZL) today reported financial results for the fiscal second quarter ended June 23, 2013.

Financial results are being presented on a continuing operations basis, excluding the discontinued trans-Pacific container shipping operations.

“Horizon Lines second-quarter adjusted EBITDA nearly doubled from the same period a year ago, driven largely by reduced vessel charter expense, lower dry-dock transit and crew-related expenses, lower fuel consumption, higher non-transportation revenue, reduced overhead and gains on the sale of assets,” said Sam Woodward, President and Chief Executive Officer. “The positive factors driving adjusted EBITDA growth were partially offset by reduced container volume and increased vessel operating expenses. Second-quarter results demonstrate that we are executing on our plan to improve Horizon Lines’ financial performance.”

Second-Quarter 2013 Financial Highlights

Volume, Rate & Fuel Cost – Container volume for the 2013 second quarter totaled 56,159 revenue loads, down 6.0% from 59,768 loads for the same period a year ago. The decline was primarily a result of the reduced number of sailings between Jacksonville and San Juan. Unit revenue per container totaled $4,263 in the 2013 second quarter, compared with $4,269 a year ago. Second-quarter unit revenue per container, net of fuel surcharges, was $3,250, up 2.6% from $3,168 a year ago. Vessel fuel costs averaged $659 per metric ton in the second quarter, 10.1% below the average price of $733 per ton in the same quarter a year ago.

Operating Revenue – Second-quarter operating revenue declined 4.1% to $259.8 million from $270.9 million a year ago. The factors driving the $11.1 million revenue decrease were an $11.5 million volume contraction, largely due to reduced sailings out of Jacksonville, and lower fuel surcharges of $8.2 million. These items were partially offset by a $4.5 million increase in container revenue rates, and a $4.1 million rise in non-transportation revenue. The improvement in non-transportation revenue was primarily due to an increase in certain transportation services agreements and other services.

Operating Income – Operating income for the second quarter totaled $16.0 million, compared with $1.0 million a year ago. The $15.0 million improvement was primarily driven by a $3.9 million reduction in vessel lease expense, $2.9 million in lower dry-dock transit and crew-related expenses, and a $2.5 million improvement in fuel recovery primarily due to lower fuel consumption. 2013 second-quarter operating income includes expenses totaling $0.5 million primarily associated with the return of excess equipment related to the 2012 fourth-quarter service change in Puerto Rico. 2012 second-quarter operating income includes $1.2 million of antitrust-related legal expense, refinancing costs, an impairment charge and severance expense. Excluding these items, second-quarter 2013 adjusted operating income totaled $16.5 million, compared with $2.2 million a year ago. (See reconciliation tables for specific line-item amounts.)

EBITDA – EBITDA totaled $28.8 million for the 2013 second quarter, compared with negative $0.6 million for the same period a year ago. Adjusted EBITDA for the second quarter of 2013 was $29.2 million, an increase of 92.1% from $15.2 million for 2012. EBITDA and adjusted EBITDA for the 2013 and 2012 second quarters were impacted by the same factors affecting operating income. Additionally, 2013 adjusted EBITDA reflects the exclusion of $0.1 million of non-cash gains on marking the conversion feature in the company’s convertible debt to fair value. Adjusted EBITDA for the 2012 second quarter also reflects the exclusion of a primarily non-cash net loss of $14.9 million, resulting from a $47.7 million loss on the conversion of debt to equity, which was partially offset by a $32.8 million gain on marking the conversion feature of the company’s convertible debt to fair value. (See reconciliation tables for specific line-item amounts.)

Net Loss – The second-quarter net loss from continuing operations totaled $0.9 million, or $0.02 per share, on a weighted average of 35.6 million shares outstanding. This compares with a year-ago net loss of $31.1 million, or $1.55 per share, on a weighted average of 20.1 million shares outstanding. On an adjusted basis, the second-quarter net loss from continuing operations totaled $0.1 million, or $0.00 per share, compared with an adjusted net loss of $14.8 million, or $0.74 per share, a year ago. The 2013 and 2012 second-quarter net losses reflect the same items impacting adjusted EBITDA. Additionally, the adjusted net loss for the 2013 second quarter excludes the non-cash accretion of the estimated multi-employer pension plan withdrawal liability related to our move from Elizabeth, New Jersey to Philadelphia, Pennsylvania, and the adjusted net loss for both the 2013 and 2012 periods excludes the non-cash accretion of payments associated with antitrust-related legal settlements, and includes the tax impact of the adjustments. (See reconciliation tables for specific line-item amounts.)

Six-Month Results – For the first half of fiscal 2013, operating revenue decreased 5.6% to $504.3 million from $534.3 million for the same period in 2012. EBITDA totaled $37.2 million compared with $5.1 million a year ago. First-half 2013 adjusted EBITDA totaled $42.9 million, compared with $26.0 million for the same period in 2012. The $16.9 million improvement was primarily due to the same factors impacting the second quarter performance versus the same period a year ago. These factors include a reduction in vessel lease expense, improved fuel recovery, lower dry-dock transit and crew-related expenses, reduced overhead, higher non-transportation revenue, and gains on the sale of assets, partially offset by lower volume and higher vessel operating expenses. The net loss from continuing operations for the 2013 six-month period totaled $20.9 million, or $0.59 per share on 35.2 million weighted average shares outstanding, compared with a net loss of $57.9 million, or $5.00 per share on 11.6 million weighted average shares outstanding, for the prior year. The adjusted net loss from continuing operations for the 2013 six-month period totaled $14.6 million, or $0.41 per share, compared with an adjusted net loss from continuing operations of $35.9 million, or $3.09 per share, for the comparable year-ago period. (See reconciliation tables for specific line items excluded from adjusted EBITDA and adjusted net loss.)

Shares Outstanding – The company had a weighted daily average of 35.6 million shares outstanding for the second quarter of 2013, and 35.2 million weighted average shares outstanding for the first six months of the year. In 2012, the company had a weighted daily average of 20.1 million shares outstanding for the second quarter, and 11.6 million shares outstanding for the six-month period. Shares outstanding reflect the company’s financial restructuring and 1-for-25 reverse stock split in the fourth quarter of 2011, a mandatory debt-for-equity exchange in the first quarter of 2012, and a further financial restructuring in the second quarter of 2012. At July 26, 2013, the equivalent of 92.5 million fully diluted shares of the company’s stock was outstanding, consisting of 35.7 million shares of common stock and warrants convertible into 56.8 million shares of common stock.

Liquidity & Debt Structure – The company had total liquidity of $40.5 million as of June 23, 2013, consisting of cash of $13.8 million and $26.7 million available under its asset-based loan (ABL) revolving credit facility. Funded debt outstanding totaled $532.4 million, consisting of: $221.6 million of 11.00% first-lien secured notes due October 15, 2016; $171.0 million of 13.00% – 15.00% second-lien secured notes due October 15, 2016, bearing interest at 15.00% being paid in kind with additional second-lien secured notes; $32.5 million drawn on the ABL facility, maturing October 5, 2016, and bearing interest at a weighted average of 4.03%; a $75.8 million term loan to fund the January 2013 purchase of the company’s Alaska vessels, bearing interest at 10.25% and maturing September 30, 2016; a $20.0 million super-priority term loan, also for purchase of the Alaska vessels, bearing interest at 8.00% and maturing September 30, 2016; $2.0 million of 6.00% convertible notes, due April 15, 2017; and $9.5 million in capital leases. The company’s weighted average interest rate for funded debt was 11.61%. Availability under the ABL credit facility is based on a percentage of eligible accounts receivable and customary reserves, with a maximum of $100.0 million of borrowing availability. Letters of credit issued against the ABL facility totaled $13.2 million at June 23, 2013.

Please see attached schedules for the reconciliation of second-quarter 2013 and 2012 reported GAAP results and Non-GAAP adjusted results.

Outlook

Management continues to expect full fiscal year revenue container volume, excluding the loss of revenue loads associated with the reduced number of sailings between Jacksonville and San Juan, and rates to be slightly higher than 2012 levels. Revenue container rate increases are necessary to mitigate contractual and inflationary growth in expenses, including the company’s vessel payroll and benefits, stevedoring, port charges, wharfage, inland transportation, and rolling stock costs, among others.

During 2012, the company dry-docked four vessels and incurred considerable transit expenses associated with the dry-docking in Asia of three of the vessels currently serving its East Coast operations. Although the company also intends to dry-dock four vessels this year, the expenses will be significantly below those incurred in 2012, due to the much shorter transit and out-of-service times for these West Coast vessels.

Vessel lease expense in 2013 will be approximately $13.8 million lower than in 2012, due to the January acquisition of three Jones Act-qualified vessels that were previously chartered. The lower vessel lease expense will be partially offset by approximately $8.5 million of additional interest expense in 2013 in connection with debt incurred for the acquisition of the vessels.

The company continues to expect overhead savings related to the reduction of its non-union workforce, completed in the first quarter of 2013, beyond the reductions associated with the Puerto Rico service change. We continually evaluate our processes for potential efficiencies and have employed numerous cost savings initiatives. For example, our move

from Elizabeth, New Jersey to Philadelphia will produce significant advantages for our customers and will also yield long term-cost efficiencies for us. These reductions will be partially offset by higher incentive and stock-based compensation, as well as other administrative expenses.

As a result of these factors, management continues to expect 2013 financial results will significantly exceed 2012 results, with 2013 adjusted EBITDA projected between $85.0 million and $97.0 million, compared with $66.0 million in fiscal 2012.

The company remains focused on continuing to further improve liquidity. Based upon our current level of operations, we believe cash flow from operations and available cash, together with borrowings available under the ABL Facility, will be adequate to meet our liquidity needs for the remainder of fiscal 2013. Total liquidity during the remainder of 2013 is expected to range between a low of approximately $45.0 million at the end of fiscal July to a high of approximately $60.0 million at the end of fiscal December.

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 and results excluding certain expenses and income, 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 press 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 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 owns a fleet of 13 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, “believe,” “anticipate,” “plan,” “targets,” “projects,” “will,” “expect,” “would,” “could,” “should,” “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: volatility in fuel prices; decreases in shipping volumes; our ability to maintain adequate liquidity to operate our business; our ability to make interest payments on our outstanding indebtedness; work stoppages, strikes and other adverse union actions; the reaction of our customers and business partners to our announcements and filings, including those referred to herein; prices for our services; government investigations and legal proceedings; suspension or debarment by the federal government; failure to comply with safety and environmental protection and other governmental requirements; failure to comply with the terms of our probation; 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 successful start-up of any Jones-Act competitor; failure to comply with the various ownership, citizenship, crewing, and U.S. build requirements dictated by the Jones Act; the arrest of our vessels by maritime claimants; severe weather and natural disasters; and 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 2012 Form 10-K filed with the SEC on March 12, 2013, 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 amounts)

Horizon Lines, Inc.

Unaudited Condensed Consolidated Statements of Cash Flows

(in thousands)

Horizon Lines, Inc.

Adjusted Operating Income (Loss) Reconciliation

(in thousands)

Horizon Lines, Inc.

Adjusted Net Loss Reconciliation

(in thousands)

Horizon Lines, Inc.

Adjusted Net Loss 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 to facilitate internal comparisons to competitors’ results and the marine container shipping and logistics industry in general. Adjusted EBITDA excludes certain charges in order to evaluate our operating performance, and when determining the payment of discretionary bonuses.

Horizon Lines, Inc.

2013 Estimated EBITDA and Adjusted EBITDA Reconciliation

(in thousands)

# # #