Exhibit 99.4

HORIZON LINES, INC. ANNOUNCES PRICING AND SATISFACTION OF THE CONSENT CONDITION FOR ITS TENDER OFFER

Charlotte, North Carolina, July 31, 2007 — Horizon Lines, Inc. (the “Company”) (NYSE: HRZ) announced today the pricing terms for its previously announced debt tender offer. The Company has offered to purchase any and all of the 9.00% Senior Notes due 2012 (CUSIP No. 44043YAB8) of its subsidiaries Horizon Lines, LLC and Horizon Lines Holding Corp. (the “Senior Notes) and 11.00% Senior Discount Notes due 2013 (CUSIP No. 40422RAB2) of its subsidiary H-Lines Finance Holding Corp. (the “Senior Discount Notes” and together with the Senior Notes, the “Notes”). The terms and conditions of the tender offer are described in detail in the Offer to Purchase and Consent Solicitation Statement (“Offer to Purchase”) dated July 17, 2007, and the related Letter of Transmittal, which were mailed to the holders of the Notes.

The total consideration for each series of Notes is based on the applicable reference U.S. Treasury security yield, which was determined at 2:00 p.m., New York City time, on July 27, 2007, by the dealer manager, plus a fixed spread as set forth in the Offer to Purchase. Holders of Notes subject to the tender offer who validly tendered, and did not validly withdraw their tender, on or before 5:00 p.m., New York City time, on July 30, 2007 (the “Consent Expiration”), are eligible to receive the total consideration if such tendered notes are accepted for purchase. Holders of Notes subject to the tender offer who validly tender their Notes after the Consent Expiration and on or before 12:00 midnight, New York City time, on Monday, August 13, 2007, and do not validly withdraw their tender, and whose Notes are accepted for purchase will receive the applicable tender offer consideration.

The Company also announced that, for both the Senior Notes and the Senior Discount Notes, it has received consents from holders representing in excess of a majority in aggregate principal amount of the outstanding Notes in such series and that, in each case, the consent condition related to the tender offer has been satisfied. Following receipt of the consents described above, the Company, Horizon Lines, LLC and Horizon Lines Holding Corp. and certain of the Company’s subsidiaries and The Bank of New York Trust Company, N.A., as trustee, executed a supplemental indenture to each of the indentures governing the Senior Notes and the Senior Discount Notes, providing for the amendments to the indentures described in the Offer to Purchase. These amendments will become operative on the date that the Company accepts for purchase the Senior Notes and the Senior Discount Notes that are validly tendered and not validly withdrawn in the tender offer, which is expected to be on or prior to August 13, 2007.

Subject to market conditions and other factors, the Company intends to finance the tender offer with a portion of the proceeds from the sale of up to $300 million of its convertible debt securities and the replacement of the Company’s existing credit facility with a new credit facility consisting of a $125 million term loan and a $200 million revolver (collectively, the “New Financing”). The Company’s obligation to accept for purchase and to pay the consideration for the Notes validly tendered in the tender offer is subject to, and conditioned upon, the completion and close of the New Financing on terms and

conditions satisfactory to the Company, and receipt by the Company of net proceeds from the New Financing sufficient to repay the Company’s indebtedness under the existing credit facility and to purchase all Notes pursuant to the Offer and certain other customary conditions.

As of 5:00 p.m., New York City time, on July 30, 2007, approximately 95.82% of the outstanding principal amount of the Senior Notes have been validly tendered and approximately 98.75% of the outstanding principal amount of the Senior Discount Notes have been validly tendered. The tender offer will expire at 12:00 midnight, New York City time, on August 13, 2007.

The tender offer is being made only pursuant to the Offer to Purchase and related Letter of Transmittal and Consent dated July 17, 2007. The Company has retained Goldman, Sachs & Co. to serve as the exclusive Dealer Manager and Solicitation Agent for the tender offer and D.F. King & Co., Inc. to serve as the Information Agent. Requests for documents may be directed to D.F. King & Co., Inc. by telephone at 800-714-3313 (toll-free). Questions regarding the tender offer and consent solicitation may be directed to Goldman, Sachs & Co. at 800-828-3182 (toll-free) or 212-357-0775.

The Offer to Purchase and this notice does not constitute an offer to sell or a solicitation of an offer to buy any securities. The convertible debt securities with which the Company intends to finance the tender offer have not been and will not be registered under the Securities Act of 1933, and as a result, such securities may not be offered or sold absent registration or an applicable exemption from registration.

Some of the statements contained in this press release are forward-looking statements, as such term is defined in the Private Securities Litigation Reform Act of 1995. These statements are based on management’s beliefs and assumptions and on information currently available to management. Actual results could differ materially from those contemplated by the forward-looking statement as a result of factors, risks and uncertainties, including uncertainties and volatility in the credit markets that could delay or prevent any new financing; the Company’s substantial indebtedness and ability to meet payment obligations; covenants contained in existing indebtedness that restrict the Company’s business operations; downgrade in the Company’s credit ratings; the Company’s inability to repurchase outstanding notes; decreases in shipping volumes; the Company’s failure to renew its commercial agreements with Maersk; rising fuel prices; labor interruptions or strikes; job related claims, liability under multi-employer pension plans; compliance with safety and environmental protection and other governmental requirements; new statutory and regulatory directives in the United States addressing homeland security concerns; the successful start-up of any Jones-Act competitor; increased inspection procedures and tighter import and export controls; restrictions on foreign ownership of the Company’s vessels; repeal or substantial amendment of the coastwise laws of the United States, also known as the Jones Act; escalation of insurance costs, catastrophic losses and other liabilities; the arrest of the Company’s vessels by maritime claimants; severe weather and natural disasters; the Company’s inability to exercise its purchase options for its chartered vessels; the aging of the Company’s

vessels; unexpected substantial drydocking costs for the Company’s vessels; the loss of the Company’s key management personnel; and changes in tax laws or in their interpretation or application, adverse tax audits and other tax matters. For a discussion of these risks and other factors that could cause actual results to differ materially from results referred to in the forward-looking statements, see the risk factors that are discussed in the Company’s Annual Report on Form 10-K for the year ended December 24, 2006 filed with the Commission. The Company does not have any obligation to update publicly any forward-looking statements, whether as a result of new information, future events or otherwise.

Media Contact:

Michael Avara of Horizon Lines, Inc.

1-704-973-7000

mavara@horizonlines.com