Exhibit 99.2

Horizon Lines Announces Organization Changes and Senior Management Promotions

CHARLOTTE, NC (August 13, 2007) Charles G. (Chuck) Raymond, Chairman, President and Chief Executive Officer of Horizon Lines, Inc. (NYSE: HRZ), announced today several organization changes, key executive promotions and a realignment of senior management responsibilities.

Effective September 1, 2007, Horizon Lines, Inc. is structuring its transportation and logistics operations under two wholly-owned subsidiaries, Horizon Lines, LLC, and Horizon Logistics, LLC. Horizon Lines, LLC, will continue as the nation’s leading Jones Act container shipping company, with a fleet of 21 U.S.-flag vessels and service routes linking the continental United States with Alaska, Hawaii, Guam, Micronesia and Puerto Rico. Horizon Logistics, LLC, is being established to manage the Company’s growing integrated logistics services, including rail, trucking and distribution operations, in addition to Horizon Services Group, an organization with a diversified offering of transportation management systems and customized software solutions being marketed to shippers, carriers, and other supply chain participants.

As a result of the business reorganization, Horizon Lines will make the following executive promotions and realign senior management responsibilities.

John Keenan will serve as President, Horizon Lines, LLC. In his new role, Mr. Keenan will be responsible for all core ocean transportation services in the Alaska, Hawaii, Guam, Micronesia and Puerto Rico markets. These responsibilities will include all port, terminal and vessel operations, sales and marketing, and service delivery functions. Mr. Keenan joined the Company in 1983 and has held numerous senior leadership positions in both sales and operations, including his most current role of Senior Vice President and Chief Transportation Officer of Horizon Lines, Inc. A 27-year veteran of the transportation industry, he began his career in 1979 with the Marine Engineers Benevolent Association, sailing in the capacity of vessel engineer. He holds a B.E. in Marine Engineering from the State University of New York at Fort Schuyler and an M.B.A. from the University of Tennessee. John will continue to be based in Dallas.

Brian Taylor will serve as President, Horizon Logistics, LLC, a new, wholly owned subsidiary of Horizon Lines, Inc. focused on integrated logistics services. Mr. Taylor’s responsibilities will include growing the Company’s logistics services capabilities and businesses, including rail, truck and distribution operations, in addition to Horizon Services Group, the Company’s technology subsidiary. Mr. Taylor has more than 23 years of service with the Company and has held several senior leadership positions, including Vice President and General Manager of our Puerto Rico and Hawaii / Guam trade lanes and General Manager of Buyers and Shippers Consolidated, BSE, Hong Kong, an affiliate of a predecessor company. He has been in his most recent position of Senior Vice President, Sales and Marketing, since February 2006. He received his B.A.

and M.B.A. in Business and Financial Management from Concordia College. Brian will continue to be based in Charlotte, N.C.

John Keenan and Brian Taylor, along with Mark Urbania, Executive Vice President and Chief Financial Officer, and John Handy, Executive Vice President, will report to Chuck Raymond, Chairman, President and Chief Executive Officer of Horizon Lines, Inc.

“This change in organizational structure allows us to stay focused on our core Jones Act transportation operations while at the same time provides for the future growth and development of our fully integrated logistics services,” said Mr. Raymond. “I believe that these promotions and realignment of management responsibilities position Horizon Lines to significantly grow our business and achieve exceptional results for our shareholders. Both John Keenan and Brian Taylor bring a tremendous amount of experience, dedication and passion to their new roles and their leadership is well respected by the rest of our organization and within the industry.

“As the above appointments demonstrate, in addition to facilitating the growth and progress of Horizon Lines, the changes we are making will allow us to provide important growth opportunities for some of our most accomplished leaders. These changes will also allow us to be more flexible in servicing our customers’ transportation and logistics needs so we remain a company that is Always There, Always Delivering.”

About Horizon Lines

Horizon Lines, Inc. is the nation’s leading Jones Act container shipping and integrated logistics company with a fleet of 21 U.S.-flag vessels and service routes linking the continental United States with Alaska, Hawaii, Guam, Micronesia and Puerto Rico. A fully integrated service provider of ocean transportation, trucking, terminal and warehousing operations, Horizon Lines also owns Horizon Services Group, an organization with a diversified offering of transportation management systems and customized software solutions being marketed to shippers, carriers, and other supply chain participants. Horizon Lines, Inc. 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, “believe,” “expect,” “anticipate,” “estimate,” “intend,” “plan,” “target,” “projects,” “likely,” “will,” “would,” “could,” and similar expressions or phrases identify forward-looking statements.

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 statements, whether as a result of new information, future events or otherwise. See the section entitled “Risk Factors” in our Form 10-K

for the fiscal year ended December 25, 2005 as filed with the SEC or in our prospectus filed with the SEC pursuant to Rule 424(b)(3) on November 17, 2006 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 to, or effects on, us. Given these uncertainties, prospective investors are cautioned not to place undue reliance on such forward-looking statements.