Exhibit 99.1

PRESS RELEASE

HORIZON LINES EXPANDS BOARD OF DIRECTORS

TO 11 MEMBERS FROM EIGHT

Seven New Board Members Join Four Existing Directors; Four Directors Retire

CHARLOTTE, NC (November 14, 2011) – Horizon Lines, Inc. (OTCQB: HRZL), the nation’s leading domestic ocean shipping company, today announced that it will expand its Board of Directors to 11 members from eight, effective November 25, 2011. In conjunction with the expansion, seven new directors will be appointed and four of the existing eight directors will retire. The board changes and expansion are as follows.

“I want to express my heartfelt appreciation to our four retiring directors for their dedicated, exemplary and long-standing service to Horizon Lines,” said Mr. Mandl. “I also welcome our new directors, whose extensive experience will serve us well as we move forward following the comprehensive refinancing of our entire capital structure last month.”

The seven new board members were nominated by the existing Board of Directors in consultation with certain of the company’s note holders, who funded the comprehensive $652.8 million refinancing on October 5, 2011. The expanded board will be comprised of four Class I directors, four Class II directors and three Class III directors. The terms of Class I, II and III directors expire at the company’s annual meeting of stockholders in 2012, 2013 and 2014, respectively.

New Directors

Jeffrey A. Brodsky, Class I Director, is currently leading Quest Turnaround Advisors LLC in its role as Plan Administrator of Adelphia Communications Corporation and is Trust Administrator of the Adelphia Recovery Trust. Mr. Brodsky co-founded Quest, a financial advisory and restructuring firm in Rye Brook, NY, in 2000, and has been a Managing Director of Quest since that time. Mr. Brodsky is currently Chairman of the Board of Directors of AboveNet, Inc., and a director of Euramax International, Inc., and inMotion, Inc. He holds a Bachelor’s degree from New York University College of Business and Public Administration, and a Master’s degree from its Graduate School of Business. He is a Certified Public Accountant.

Kurt M. Cellar, Class I Director, has been a self-employed consultant and board member since January 2008. From July 1999 through January 2008, he was a partner and Portfolio Manager at Bay Harbour Management, L.C. Prior to that, he was an associate at Remy Investors and Consultants, Inc., where he sourced and analyzed public and private investment opportunities. Prior to Remy, Mr. Cellar was an associate at LEK/Alcar Consulting Group, Inc., a strategic management consulting firm. Mr. Cellar currently serves on the boards of Angiotech Pharmaceuticals, Inc., Aventine Renewable Energy Holdings, Inc., Hawaiian Telecom Holdco, Inc., Six Flags Entertainment Corporation, U.S. Concrete, Inc., and Vertis Communications. Mr. Cellar received a Bachelor’s degree in Economics and Business from the University of California, Los Angeles and an M.B.A. in Finance and Entrepreneurial Management from the Wharton School at the University of Pennsylvania.

Carol B. Hallett, Class II Director, has been of counsel to the U.S. Chamber of Commerce since 2003. From 1995 to 2003, Mrs. Hallett was President and Chief Executive Officer of the Air Transport Association of America (ATA), the nation’s oldest and largest airline trade association. Prior to joining the ATA, Mrs. Hallett served as senior government relations advisor with Collier, Shannon, Rill & Scott from 1993 to 1995. She has been a member of the Commercial Operations Advisory Committee of Customs & Border Protection, appointed by the Secretaries of Treasury and Homeland Security, since 2011. Mrs. Hallett has served as a member of the Board of Directors of Atlas Air Worldwide Holdings, Inc., and G4S Government Solutions (formerly Wackenhut Services, Inc.) since 2006, and Rolls Royce-North America since 2003.

James LaChance, Class III Director, has been a director of FriendFinder Networks, Inc. since 2008. Since 2004, Mr. LaChance has served as the non-executive Chairman of the Board of Northern Offshore Ltd., a drilling and production services company. From July 2005 to February 2008, Mr. LaChance served as portfolio manager at Satellite Asset Management, L.P., an investment management fund in New York with approximately $7 billion under management. From 2002 to June 2005, he was a partner at Post Advisory Group LLC, an investment management firm in Los Angeles with $8 billion under management. Mr. LaChance began his career as an audit and management consultant for Arthur Andersen & Co. He graduated from Northeastern University with a Bachelor’s degree in Business Administration and received an M.B.A. from the Stern School of Business at New York University.

Steven L. Rubin, Class III Director, is Principal of InterPro Advisory LLC, a consulting practice serving the container shipping, intermodal and chassis markets. Between April 2008 and June 2011, Mr. Rubin was President and CEO of TRAC Intermodal, North America’s largest chassis leasing company. He is also currently the Chairman of the Board of Directors of the Intermodal Association of North America, the premier trade association representing the combined interests of the intermodal freight industry. Prior to joining TRAC, Mr. Rubin spent 17 years at Kawasaki Kisen Kaisha, Inc. (K Line), Japan’s third-largest shipping company, in a number of roles for North American operations. Mr. Rubin graduated from the University of Pennsylvania and the Wharton School with a B.A. in History and B.S. in Economics, respectively. He received his M.B.A. from the Stern School of Business at New York University, with a concentration in accounting, and obtained his Certified Public Accountant license in the state of New York.

Martin Tuchman, Class II Director, is Chief Executive Officer of the Tuchman Group, which overseas holdings in real estate, banking and international shipping, and has headed Kingstone Capital V, a private investment group, since 2007. Since March 2011, Mr. Tuchman has served on the Board of Directors for Sea Cube Container Leasing Ltd. Since December 2008, Mr. Tuchman has served as the Vice Chairman of the First Choice Bank in Lawrenceville, N.J. In 1968, after helping develop the current standard for intermodal containers and chassis in connection with the American National Standards Institute, Mr. Tuchman co-founded Interpool, Inc., a leading container leasing business, which was sold to funds affiliated with Fortress Investment Group LLC, in 2007. In 1987, Mr. Tuchman formed Trac Lease, a chassis leasing company which was subsequently merged into Interpool, Inc. Mr. Tuchman holds a Bachelor of Science degree in Mechanical Engineering from the New Jersey Institute of Technology and an M.B.A. from Seton Hall University.

David N. Weinstein, Class I Director, has served as a business consultant specializing in corporate restructurings since September 2008. Prior to this role, he served as Managing Director at Calyon Securities, a global provider of commercial and investment banking products and services for corporations and institutional clients, from March 2007 to August 2008. Prior to that, he was a consultant specializing in business reorganization and capital market activities. Mr. Weinstein has also served as a Managing Director and Head of High Yield Capital Markets at BNP Paribas, BankBoston Securities and Chase Securities, Inc., and head of the capital markets group in the high yield department at Lehman Brothers. Mr. Weinstein currently serves on the board of directors of Deep Ocean Group Holding AS, Georgia Gulf Corporation and Granite Broadcasting Corporation. He has previously served as Chairman of the Board of Pioneer Companies, Inc. and York Research Corporation, and as a director of Interstate Bakeries Corporation. Mr. Weinstein holds a Bachelor’s degree from Brandeis University and a Juris Doctorate from the Columbia University School of Law.

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.

# # #