Exhibit 99.2

HORIZON LINES, INC.

Offer to Exchange and Consent Solicitation

Pursuant to the Prospectus, dated August 26, 2011

for Any and All of the

4.25% Convertible Senior Notes due 2012

(CUSIP No. 44044K AB7) and

Solicitation of Consents to Proposed Amendments to the Related Indenture

August 26, 2011

THE EXCHANGE OFFER AND THE CONSENT SOLICITATION WILL EXPIRE AT 11:59 P.M., NEW YORK CITY TIME, ON SEPTEMBER 23, 2011, UNLESS EXTENDED OR EARLIER TERMINATED BY US (SUCH DATE AND TIME, AS THE SAME MAY BE EXTENDED, THE “EXPIRATION DATE”). TENDERS MAY BE WITHDRAWN AT ANY TIME BEFORE 11:59 P.M., NEW YORK CITY TIME, ON THE EXPIRATION DATE (SUCH DATE AND TIME, AS THE SAME MAY BE EXTENDED, THE “WITHDRAWAL DEADLINE”)

To Brokers, Dealers, Commercial Banks,

Trust Companies and Other Nominees:

We are enclosing the documents listed below relating to the offer by Horizon Lines, Inc. (the “Company”) to exchange (the “Exchange Offer”) (i) the number of shares of its common stock or warrants or redemption notes, as the case may be, and (ii) new notes for each $1,000 of principal amount of outstanding 4.25% Convertible Senior Notes due 2012 (the “old notes”) as set forth in the summary offering table on the inside front cover of the prospectus dated August 26, 2011, as filed with the Securities and Exchange Commission (as may be amended or supplemented, the “Prospectus”), in accordance with and subject to the terms and conditions set forth in the Prospectus, a copy of which accompanies this letter, and the letter of transmittal (as each may be amended or supplemented from time to time) (collectively, the “Offer Documents”). Certain terms used and not defined herein shall have the respective meanings ascribed to them in the Prospectus.

Concurrently with the Exchange Offer, the Company is soliciting consents (the “Consent Solicitation”) from the holders of the old notes to amend (the “Proposed Amendments”) the terms of the indenture governing the old notes. The Proposed Amendments would eliminate or amend substantially all of the restrictive covenants, and modify certain of the events of default and various other provisions of the indenture. Each holder that tenders old notes in the Exchange Offer will be deemed to have consented to the Proposed Amendments. Holders may not deliver consents to the Proposed Amendments without tendering their old notes, and holders may not tender their old notes without delivering consents.

We are requesting that you contact your clients for whom you hold old notes through your account (the “Beneficial Holders”) with The Depository Trust Company (“DTC”) regarding the Exchange Offer or Consent Solicitation. For your information and for forwarding to your clients for whom you hold old notes registered in your name or in the name of your nominee, we are enclosing the following documents:

1. a form of letter which may be sent to your clients for whose account you hold old notes through your DTC account, which contains a form that may be sent from your clients to you with such clients’ instruction with regard to the Exchange Offers and Consent Solicitation;

2. Letter of Transmittal (together with accompanying Substitute Form W-9 and related Guidelines); and

3. a copy of the appropriate Offer Documents.

YOUR PROMPT ACTION IS REQUESTED. OLD NOTES TENDERED PURSUANT TO THE EXCHANGE OFFER MAY BE WITHDRAWN AT ANY TIME BEFORE THE EXPIRATION DATE. WE URGE YOU TO CONTACT YOUR CLIENTS AS PROMPTLY AS POSSIBLE IN ORDER TO OBTAIN THEIR INSTRUCTIONS.

We will pay brokerage houses and other custodians, nominees and fiduciaries their reasonable out-of-pocket expenses incurred in connection with forwarding copies of the Offer Documents and related documents to the beneficial owners of old notes and in connection with handling or forwarding tenders for exchange and payment. We will pay or cause to be paid any transfer taxes applicable to the tender of old notes.

Any inquiries you may have with respect to Exchange Offer or the Consent Solicitations for the Proposed Amendments, or requests for additional copies of the enclosed materials or the Letter of Transmittal, should be directed to Global Bondholder Services Corporation, 65 Broadway – Suite 404, New York, New York 10006 Attention: Corporate Actions, (212) 430-3774 or fax (212) 430-3775.

Please refer to “General Terms of the Exchange Offer and Consent Solicitation—Procedures for Tendering Old Notes” in the Prospectus for a description of the procedures which must be followed to tender old notes in the Exchange Offer and participate in the consent solicitations for the Proposed Amendments.

Very truly yours,

Horizon Lines, Inc.

NOTHING CONTAINED HEREIN OR IN THE ENCLOSED DOCUMENTS SHALL CONSTITUTE YOU OR ANY OTHER PERSON AS THE AGENT OF THE COMPANY OR THE EXCHANGE AGENT, OR AUTHORIZE YOU OR ANY OTHER PERSON TO USE ANY DOCUMENT OR TO MAKE ANY STATEMENT ON BEHALF OF ANY OF THEM IN CONNECTION WITH THE EXCHANGE OFFER OTHER THAN THE DOCUMENTS ENCLOSED HEREWITH AND THE STATEMENTS CONTAINED THEREIN.

Enclosures