Exhibit 99.1

PRESS RELEASE

HORIZON LINES NAMES SAM WOODWARD

PRESIDENT AND CHIEF EXECUTIVE OFFICER

Appointment Follows Annual Stockholder Meeting

CHARLOTTE, NC, June 7, 2012 – Horizon Lines, Inc. (OTCQB: HRZL), one of the nation’s leading domestic ocean shipping companies, today announced that Sam Woodward has joined the company as President and Chief Executive Officer (CEO) and has been appointed to the company’s Board of Directors, effective June 7, 2012. Mr. Woodward succeeds Stephen H. Fraser, who has served as interim President and CEO since March 2011, and who will also step down from the company’s Board of Directors, effective June 7, 2012.

“We are delighted that Sam has chosen to join Horizon Lines as President and CEO,” said Jeffrey A. Brodsky, Chairman of the Board of Directors. “Sam brings extensive transportation and logistics experience, and is known for his leadership abilities as a business strategist focused on operational transformation and excellence. He has a strong track record of success in a career that has spanned multiple companies over more than 30 years. Sam’s proven leadership abilities will be an asset to management and the Board, as Horizon Lines moves forward in the years ahead.

“We also want to thank Stephen for his leadership of Horizon Lines as interim President and CEO over the past 15 months,” Mr. Brodsky said. “Stephen successfully shepherded Horizon through a very challenging period. We wish Stephen well in his future endeavors and we are confident this transition will be a seamless one for our customers and other stakeholders.”

Mr. Woodward, 63, joins Horizon Lines from Traffic Tech Inc., an international freight forwarder, where he held several executive leadership roles. He also served as a managing director of Bengur Bryan & Co., a middle market investment bank, where since 2008 he headed the firm’s Transportation and Business Process Outsourcing Practice. From 2004 to 2008, Mr. Woodward was Chairman, President and CEO of Gemini Air Cargo, Inc. Prior to Gemini, Mr. Woodward was president of SAW Investment Services, his own investment firm, where he oversaw investment and management services in the U.S. freight- and logistics-based technology markets. From 1994 to 1999, Mr. Woodward served at YRC

Worldwide as Senior Vice President, Operations and Planning, managing operations and strategy of the company’s portfolio of transportation and logistics companies.

“I look forward to working with the many talented and dedicated associates and stakeholders of Horizon Lines, as we move forward to grow the business in our three core trade lanes,” Mr. Woodward said.

Annual Stockholder Meeting Results

Mr. Woodward was appointed President and CEO, as well as a Director, at a meeting of the Board of Directors that followed the company’s 2012 annual stockholder meeting today. At the annual meeting, shareholders elected Mr. Brodsky, Kurt M. Cellar and David N. Weinstein Class I Directors, and ratified the appointment of Ernst & Young, LLP as the company’s independent registered public accounting firm for the fiscal year ending December 23, 2012. Additionally, shareholders provided a non-binding advisory vote approving the compensation paid to the company’s named executive officers.

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.

# # #