Exhibit 99.1

HORIZON LINES SUCCESSFULLY AMENDS CREDIT AGREEMENT

CHARLOTTE, N.C., Dec. 12, 2006 – Horizon Lines, Inc. (NYSE: HRZ) reported today that it successfully amended its senior credit facility.

The primary components of the amendment to the senior credit facility include: 1) increasing the revolving credit facility by $25 million to $75 million; 2) increasing the additional term loan borrowing availability by $25 million to $75 million; 3) raising the annual capital spending limit to $40 million, exclusive of vessel and equipment lease buyouts; 4) allowing for 100% carryover of unutilized permitted annual capital spending; 5) increasing maximum restricted payments on a rolling four quarters basis from $15 million to $36 million; 6) providing 100% credit for voluntary loan prepayments on the required annual excess cash flow sweep now commencing in 2007; and 7) increasing permitted acquisitions from $30 million to $120 million annually and from $100 million to $200 million over the life of the facility. The pre-amendment senior credit facility consisted of a $250 million term loan and a $50 million revolving credit facility.

“This amendment provides Horizon Lines with the greater flexibility to meet its future growth needs in a cost effective manner,” said Mark Urbania, Senior Vice President and Chief Financial Officer. “The amendment also serves as recognition of Horizon Lines’ improved credit standing brought about by the significant de-leveraging achieved since Horizon Lines’ initial public offering in September 2005 through both earnings growth and debt prepayments. We plan to continue to de-leverage in the future via both debt prepayments and earnings growth.”

Horizon Lines, Inc. is the nation’s leading Jones Act container shipping and integrated logistics company. It accounts for approximately 36% of total U.S. marine container shipments from the continental U.S. to the three non-contiguous Jones Act markets, Alaska, Hawaii and Puerto Rico, and to Guam. Horizon Lines is publicly traded on the New York Stock Exchange under ticker symbol HRZ.

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.

SOURCE Horizon Lines, Inc.

CONTACT: Michael Avara of Horizon Lines, Inc., +1-704-973-7000, or mavara@horizonlines.com

2