Exhibit 99.1

PRESS RELEASE

For information contact:

Jim Storey

704-973-7107

HORIZON LINES TO ADJUST PUERTO RICO SERVICE SCHEDULE

Company Moving to Weekly Jacksonville Service from Twice Weekly

Change to Thursday Departure in Jacksonville

Will Improve Cargo Availability Times in San Juan

Elizabeth Service Also Moving to Thursday Departure; Houston Schedule Remains Unchanged

CHARLOTTE, NC (December 5, 2012) – Horizon Lines, Inc. (OTCQB: HRZL), one of the nation’s leading domestic ocean shipping companies, today announced it is adjusting its Puerto Rico service schedule to better align its deployed capacity with market demand and to improve cargo availability times in San Juan.

Effective January 10, 2013, the company will offer weekly service between Jacksonville, Florida, and San Juan, Puerto Rico. The southbound service will depart Jacksonville on Thursday evenings and arrive in San Juan on Sundays. Cargo will be available at the opening of business on Monday mornings. The company currently offers twice weekly service between Jacksonville and San Juan, departing Jacksonville on Tuesdays and Fridays.

Additionally, Horizon Lines weekly San Juan service from the Northeast will depart Elizabeth, New Jersey on Thursday evenings, instead of Fridays, with cargo availability in San Juan on Mondays. Northbound departures from San Juan to Elizabeth will be on Sunday evenings with arrival on Thursday mornings. Northbound departures from San Juan to Jacksonville will be Monday evenings with arrival on Thursday mornings.

Service schedules between Houston, Texas, and San Juan will remain unchanged.

This service adjustment is expected to create cost efficiencies that will enable the company to improve the Puerto Rico trade lane’s financial performance and reinvest in the business over the long term. In association with the service change, the company expects to record a fourth-quarter charge of approximately $3.6 million.

“Puerto Rico’s economy remains in a prolonged multi-year recession, during which time domestic container volumes to the island have contracted sharply,” said Richard Rodriguez, Vice President and General Manager of Puerto Rico. “After a comprehensive review of our deployments in the market, we determined Horizon can more efficiently serve Puerto Rico

Horizon Lines News Release Page 2 of 3

through one weekly Jacksonville sailing, instead of two. Adequate capacity exists on our vessel that will depart on Thursdays to serve most customers who previously shipped on our Tuesday and Friday vessels. Customers have frequently requested Monday morning cargo availability and we are excited that our new schedule will provide Sunday arrivals into San Juan so that customers can pick up freight at the opening of business Monday mornings.”

Horizon Lines will continue to operate the largest vessels in the trade, serving Puerto Rico from the three most geographically diverse U.S. ports with the most extensive intermodal network across North America.

“We intend to continue to offer timely and efficient Jacksonville service on a weekly basis,” Mr. Rodriguez said. “However, making this service change is necessary to improve cost efficiencies and better position Horizon Lines to make the investments necessary to serve our Puerto Rico customers and maintain and grow our business over the long run.”

During the past 12 months, Horizon Lines has invested approximately $30 million in an extensive upgrade program to the three vessels that will continue to serve Puerto Rico. The Horizon Navigator and the Horizon Trader, which will continue to call on Jacksonville and the Northeast, are C8 Class container vessels with nominal capacity of 1,125 forty-foot equivalent units (FEUs). The smaller Horizon Producer, with nominal capacity of approximately 840 FEUs, will continue on its regular Houston schedule. The Horizon Discovery, with nominal capacity of approximately 690 FEUs, normally carried the Tuesday cargo from Jacksonville during 2012. It will be removed from active service and used as a relief vessel.

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,” “should,” “may,” and similar expressions or phrases identify forward-looking statements.

Horizon Lines News Release Page 3 of 3

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: changes in shipping volumes; the reaction of our customers and business partners to our announcements and filings, including those referred to herein; volatility in fuel prices; work stoppages, strikes and other adverse union actions; government investigations and legal proceedings; suspension or debarment by the federal government; 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 2011 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.

# # #