REGISTRATION RIGHTS AGREEMENT by and among Horizon Lines, Inc., the Guarantors listed on the signature page hereto and the Holders party hereto Dated as of October 5, 2011 REGISTRATION RIGHTS AGREEMENT

Exhibit 10.3

EXECUTION VERSION

REGISTRATION RIGHTS AGREEMENT

by and among

Horizon Lines, Inc.,

the Guarantors listed on the signature page hereto

and

the Holders party hereto

Dated as of October 5, 2011

REGISTRATION RIGHTS AGREEMENT

This Registration Rights Agreement (this “Agreement”) is made and entered into as of October 5, 2011, by and among Horizon Lines, Inc., a Delaware corporation (the “Company”), the guarantors listed on the signature page hereto (collectively, the “Guarantors”), the investors signatory hereto (collectively, the “Initial Holders”) and any Permitted Transferee (as defined below) who hereafter becomes a party to this Agreement as contemplated by Section 7(b) of this Agreement (each such party who holds Registrable Securities (as defined below), a “Holder” and, collectively, the “Holders”).

Pursuant to the exchange offer (the “Exchange Offer”) described in the Company’s Registration Statement on Form S-4 (File No. 333-176520), the Initial Holders will exchange the Company’s existing 4.25% Convertible Senior Notes due 2012 for (i) shares of the Company’s common stock, par value $0.01 per share (“Common Stock”) (or Warrants (as defined herein) or redemption notes in lieu thereof), (ii) new 6.00% Series A Convertible Senior Secured Notes due 2017 (the “Series A Notes”) and (iii) new 6.00% Series B Convertible Senior Secured Notes (the “Series B Notes” and, together with the Series A Notes, the “New Notes”).

This Agreement is made for the benefit of the Holders. In connection with the Exchange Offer, the Company has agreed to provide the registration rights set forth in this Agreement.

The parties hereby agree as follows:

Section 1. Definitions.

As used in this Agreement, the following capitalized terms shall have the following meanings:

“Affiliate” means, with respect to any Person, any Person directly or indirectly controlling, controlled by or under common control with, such other Person. For purposes of this definition, “control” (including, with correlative meanings, the terms “controlled by” and “under common control with”) when used with respect to any Person, means the possession, directly or indirectly, of the power to cause the direction of management and/or policies of such Person, whether through the ownership of voting securities by contract or otherwise.

“Business Day” means any day other than a Saturday, Sunday or U.S. federal holiday or a day on which banking institutions or trust companies located in New York, New York are authorized or obligated to be closed. If the time to perform any action hereunder falls on a day that is not a Business Day, such time will be extended to the next Business Day and no Additional Interest shall accrue for the intervening period.

“Commission” means the Securities and Exchange Commission.

“Exchange Act” means the Securities Exchange Act of 1934, as amended.

“FINRA” means the Financial Industry Regulatory Authority, Inc.

“Indemnified Holder” has the meaning set forth in Section 5(a) hereof.

“Permitted Transferee” means any transferee of Registrable Securities in a transaction not involving a public offering; provided that such transferee agrees in writing to become a party to this Agreement.

“Person” means an individual, partnership, corporation, trust or unincorporated organization, or a government or agency or political subdivision thereof.

“Prospectus” means the prospectus included in a Shelf Registration Statement, as amended or supplemented by any prospectus supplement and by all other amendments thereto, including post-effective amendments, and all material incorporated by reference into such Prospectus.

“Registrable Securities” means (i) all Common Stock held by the Initial Holders immediately following the consummation of the Exchange Offer, (ii) all Warrants held by the Initial Holders immediately following the consummation of the Exchange Offer and the Common Stock issuable upon exercise or conversion of such Warrants, (iii) the Series A Notes held by the Initial Holders immediately following the consummation of the Exchange Offer and the Common Stock or Warrants issuable upon conversion of such Series A Notes (including the Common Stock issuable upon exercise or conversion of any such Warrants) and (iv) the Series B Notes held by the Initial Holders immediately following the consummation of the Exchange Offer and the Common Stock or Warrants issuable upon conversion of such Series B Notes (including the Common Stock issuable upon exercise or conversion of any such Warrants). Registrable Securities include any shares of capital stock, warrants or other securities of the Company issued as a dividend or other distribution with respect to or in exchange for or in replacement of Registrable Securities. As to any particular Registrable Securities, such securities shall cease to be Registrable Securities when: (a) a Registration Statement with respect to the sale of such securities shall have become effective under the Securities Act and such securities shall have been sold, transferred, disposed of or exchanged in accordance with such Registration Statement; (b) such securities shall have ceased to be outstanding; or (c) the entire amount of the Registrable Securities held by any Holder may be sold in a single sale, in the opinion of counsel reasonably satisfactory to the Holder, without any limitation as to volume or manner of sale pursuant to Rule 144 (or any successor rule or regulation) under the Securities Act.

“Registration Statement” means a registration statement filed by the Company with the Commission in compliance with the Securities Act for a public offering and sale of Registrable Securities (other than a registration statement on Form S-4 or S-8 (or any successor or substantially similar form), or in connection with (i) an employee stock option, stock purchase or compensation plan or securities issued or issuable pursuant to any such plan or (ii) a dividend reinvestment plan).

“Securities Act” means the Securities Act of 1933, as amended.

“Shelf Registration Statement” has the meaning set forth in Section 2(a) hereof and including the Prospectus included therein, all amendments and supplements thereto (including post-effective amendments) and all exhibits and material incorporated by reference therein.

2

“Warrants” means the Company’s warrants described in the Warrant Agreement dated as of the date hereof between the Company and The Bank of New York Mellon Trust Company, N.A., as warrant agent.

Section 2. Shelf Registration.

(a) Shelf Registration. The Company shall use commercially reasonable efforts to (i) cause to be filed a shelf registration statement on Form S-1 or Form S-3, as applicable, pursuant to Rule 415 under the Securities Act, which shall provide for resales, on a delayed or continuous basis, of all Registrable Securities by the Holders thereof (the “Shelf Registration Statement”), within 60 days following the date hereof and (ii) cause the Shelf Registration Statement to be declared effective under the Securities Act by no later than the 180^th day following the date hereof.

The Company shall use commercially reasonable efforts to keep such Shelf Registration Statement continuously effective, supplemented and amended as required by the provisions of Section 3 hereof to the extent necessary to ensure that it is available for resales of Registrable Securities by the Holders of such Securities entitled to the benefit of this Section 2(a), and to ensure that it conforms with the requirements of this Agreement in all material respects, the Securities Act and the policies, rules and regulations of the Commission as announced from time to time, from the date on which the Shelf Registration Statement is declared effective by the Commission until all the Registrable Securities have been sold pursuant to such Shelf Registration Statement.

(b) Provision by Holders of Certain Information in Connection with the Shelf Registration Statement. No Holder of Registrable Securities may include any of its Registrable Securities in any Shelf Registration Statement pursuant to this Agreement unless and until such Holder furnishes to the Company in writing such information as required by Regulation S-K under the Securities Act or reasonably requested by the Company for use in connection with any Shelf Registration Statement or Prospectus or preliminary Prospectus included therein. Each Holder as to which any Shelf Registration Statement is being effected agrees to furnish promptly to the Company all information required to be disclosed in order to make the information previously furnished to the Company by such Holder not materially misleading and shall promptly supply such other information as the Company may from time to time reasonably request.

(c) Certification. Within 15 Business Days following receipt of written request from the Company by any Holder whose Registrable Securities have been included in a Shelf Registration Statement (which request shall not be made more than once in any calendar year beginning with the second calendar year after the effectiveness of the Shelf Registration), such Holder shall certify to the Company that such Holder continues to hold Registrable Securities (the “Certification”). If a Holder of Registrable Securities fails to provide the Certification within the 15 Business Day period referred to in the immediately preceding sentence, the Company reserves the right, in its sole discretion, to remove such Holder’s

3

Registrable Securities from the Shelf Registration Statement within 15 Business Days after receipt by such Holder of a second written notice specifying that the Holder may be removed from the Shelf Registration Statement unless such Holder provides the Certification within such subsequent 15 Business Day period. The Company shall use commercially reasonable efforts to deliver the applicable written request(s) to any Holder.

Section 3. Registration Procedures.

(a) In connection with any Shelf Registration Statement and any Prospectus required by this Agreement to permit the sale or resale of Registrable Securities, the Company shall:

(i) use commercially reasonable efforts to keep such Shelf Registration Statement continuously effective and provide all requisite financial statements (including, if required by the Securities Act or any regulation thereunder, financial statements of the Guarantors) until all Registrable Securities have been sold; upon the occurrence of any event that would cause any such Shelf Registration Statement or the Prospectus contained therein (A) to contain a material misstatement or omission or (B) not to be effective and usable for resale of Registrable Securities during the period required by this Agreement, the Company shall file promptly an appropriate amendment to such Shelf Registration Statement, in the case of clause (A), correcting any such misstatement or omission, and, if Commission review is required, use their commercially reasonable efforts to cause such amendment to be declared effective and such Shelf Registration Statement and the related Prospectus to become usable for their intended purpose(s) as soon as practicable thereafter;

(ii) use commercially reasonable efforts to prepare and file with the Commission such amendments and post-effective amendments to the Shelf Registration Statement as may be necessary to keep the Shelf Registration Statement effective until all Registrable Securities have been sold; cause the Prospectus to be supplemented by any required Prospectus supplement, and as so supplemented to be filed pursuant to Rule 424 under the Securities Act, and to comply fully with the applicable provisions of Rules 424 and 430A under the Securities Act in a timely manner; and comply with the provisions of the Securities Act with respect to the disposition of all securities covered by such Shelf Registration Statement during the period in accordance with the intended method or methods of distribution by the sellers thereof set forth in such Shelf Registration Statement or supplement to the Prospectus;

(iii) advise each Holder whose Registrable Securities have been included in a Shelf Registration Statement, (A) when the Prospectus or any Prospectus supplement or post-effective amendment has been filed, and, with respect to such Shelf Registration Statement or any post-effective amendment thereto, when the same has become effective, (B) of any request by the Commission for amendments to the Shelf Registration Statement or amendments or supplements to the Prospectus or for additional information relating thereto, (C) of the issuance by the Commission of any stop order suspending the effectiveness of the Shelf Registration Statement under the Securities Act or of the suspension by any state securities commission of the qualification of the

4

Registrable Securities for offering or sale in any jurisdiction, or the initiation of any proceeding for any of the preceding purposes, (D) of the happening of any event that makes any statement of a material fact made in the Shelf Registration Statement, the Prospectus, any amendment or supplement thereto, or any document incorporated by reference therein untrue, or that requires the making of any additions to or changes in the Shelf Registration Statement or the Prospectus in order to make the statements therein not misleading. If at any time the Commission shall issue any stop order suspending the effectiveness of the Shelf Registration Statement, or any state securities commission or other regulatory authority shall issue an order suspending the qualification or exemption from qualification of the Registrable Securities under state securities or blue sky laws, the Company shall use commercially reasonable efforts to obtain the withdrawal or lifting of such order at the earliest possible time;

(iv) furnish without charge, upon request, to each selling Holder named in a Shelf Registration Statement, and each of the underwriter(s), if any, before filing with the Commission, copies of the Shelf Registration Statement or any Prospectus included therein or any amendments or supplements to any such Shelf Registration Statement or Prospectus (including all documents incorporated by reference after the initial filing of such Shelf Registration Statement), which documents will be subject to the review and comment of such Holders and underwriter(s) in connection with such sale, if any, for a period of at least three Business Days, and the Company will not file any such Shelf Registration Statement or Prospectus or any amendment or supplement to any such Shelf Registration Statement or Prospectus (including all such documents incorporated by reference) to which a Holder of Registrable Securities covered by such Shelf Registration Statement or the underwriter(s), if any, shall reasonably object in writing within three Business Days after the receipt thereof (such objection to be deemed timely made upon confirmation of telecopy transmission within such period). The objection of a Holder or underwriter, if any, shall be deemed to be reasonable if such Shelf Registration Statement, amendment, Prospectus or supplement, as applicable, as proposed to be filed, contains a material misstatement or omission. Notwithstanding the foregoing, the Company shall not be required to take any actions under this clause (iv) that are not, in the reasonable opinion of counsel for the Company, in compliance with applicable law;

(v) promptly prior to the filing of any document that is to be incorporated by reference into a Shelf Registration Statement or Prospectus in connection with such registration or sale, if any, provide copies of such document to each selling Holder named in the Shelf Registration Statement in connection with such exchange, registration or sale, if any, and to the underwriter(s), if any, make the Company’s representatives available for discussion of such document and other customary due diligence matters subject to execution and delivery of customary confidentiality agreements, and include such information in such document prior to the filing thereof as such selling Holders or underwriter(s), if any, reasonably may request;

(vi) make available at reasonable times for inspection by the selling Holders, the underwriter(s), if any, participating in any disposition pursuant to such Shelf Registration Statement and any attorney or accountant retained by such selling Holder or

5

any of the underwriter(s), all financial and other records, pertinent corporate documents and properties of each of the Company and the Guarantors and cause the Company’s and the Guarantors’ officers, directors and employees to supply all information reasonably requested by any such Holder, underwriter, attorney or accountant in connection with such Shelf Registration Statement or any post-effective amendment thereto subsequent to the filing thereof and prior to its effectiveness and to participate in meetings with investors to the extent requested by the underwriter(s), if any; provided that any Holder or representative thereof requesting or receiving such information shall agree to be bound by reasonable confidentiality agreements and procedures with respect thereto;

(vii) if requested by any selling Holders or the underwriter(s), if any, promptly incorporate in any Shelf Registration Statement or Prospectus, pursuant to a supplement or post-effective amendment if necessary, such information as such selling Holders and underwriter(s), if any, may reasonably request to have included therein, including, without limitation, information relating to the “Plan of Distribution” of the Registrable Securities, information with respect to the principal amount of Registrable Securities being sold to such underwriter(s), the purchase price being paid therefor and any other terms of the offering of the Registrable Securities to be sold in such offering; and make all required filings of such Prospectus supplement or post-effective amendment as soon as practicable after the Company is notified of the matters to be incorporated in such Prospectus supplement or post-effective amendment;

(viii) upon request, furnish to each selling Holder and each of the underwriter(s), if any, without charge, at least one copy of the Shelf Registration Statement, as first filed with the Commission, and of each amendment thereto, including financial statements and schedules (without all documents incorporated by reference therein or exhibits thereto, unless requested);

(ix) upon request, deliver to each selling Holder and each of the underwriter(s), if any, without charge, as many copies of the Prospectus (including each preliminary prospectus) and any amendment or supplement thereto as such Persons reasonably may request; provided, that if no Shelf Registration Statement is effective or no Prospectus is usable, the Company shall deliver to each selling Holder a notice to that effect in response to such request; each of the Company and the Guarantors hereby consents to the use (in accordance with law) of the Prospectus and any amendment or supplement thereto by each of the selling Holders and each of the underwriter(s), if any, in connection with the offering and the sale of the Registrable Securities covered by the Prospectus or any amendment or supplement thereto;

6

(x) upon the reasonable request of such Holder, enter into such agreements (including an underwriting agreement containing customary terms), and make such representations and warranties, and take all such other actions in connection therewith in order to expedite or facilitate the disposition of the Registrable Securities pursuant to a Shelf Registration Statement contemplated by this Agreement, all to such extent as may be customarily and reasonably requested by any Holder of Registrable Securities or underwriter in connection with any sale or resale pursuant to a Shelf Registration Statement contemplated by this Agreement; and whether or not an underwriting agreement is entered into and whether or not the registration is an underwritten registration, the Company shall:

(A) upon the request of any Holder, furnish to each underwriter, if any, in such substance and scope as they may reasonably request and as are customarily made by issuers to underwriters in primary underwritten offerings, upon the date of the effectiveness of the Shelf Registration Statement:

(1) an opinion and 10b-5 letter in customary form of counsel for the Company and the Guarantors, covering the matters customarily covered in opinions and 10b-5 letters requested in similar underwritten offerings and such other matters as such parties may reasonably request; and

(2) use commercially reasonable efforts to obtain a customary comfort letter, dated the date of effectiveness of the Shelf Registration Statement, from the Company’s independent accountants, in the customary form and covering matters of the type customarily requested to be covered in comfort letters by underwriters in connection with primary underwritten offerings;

(B) deliver such other documents and certificates as may be reasonably requested by such parties to evidence compliance with clause (A) above and with any customary conditions contained in the underwriting agreement or other agreement entered into by the Company or any of the Guarantors;

(xi) prior to any public offering of Registrable Securities, cooperate with the selling Holders, the underwriter(s), if any, and their respective counsel in connection with the registration and qualification of the Registrable Securities under the state securities or blue sky laws of such jurisdictions as the selling Holders or underwriter(s), if any, may request and do any and all other acts or things necessary or advisable to enable the disposition in such jurisdictions of the Registrable Securities covered by the Shelf Registration Statement;

(xii) use its commercially reasonable efforts to cause the Registrable Securities covered by the Shelf Registration Statement to be registered with or approved by such other governmental agencies or authorities as may be necessary to enable the seller or sellers thereof or the underwriter(s), if any, to consummate the disposition of such Registrable Securities;

(xiii) if any fact or event contemplated by Section 3(a)(iii)(D) hereof shall exist or have occurred, prepare a supplement or post-effective amendment to the Shelf Registration Statement or related Prospectus or any document incorporated therein by reference or file any other required document so that, as thereafter delivered to the purchasers of Registrable Securities, the Prospectus will not contain an untrue statement of a material fact or omit to state any material fact necessary in order to make the statements therein not misleading;

7

(xiv) cooperate and assist in any filings required to be made with FINRA and in the performance of any due diligence investigation by any underwriter (including any “qualified independent underwriter”) that is required to be retained in accordance with the rules and regulations of FINRA; and

(xv) otherwise use commercially reasonable efforts to comply with all applicable rules and regulations of the Commission, and make generally available to its security holders, as soon as practicable, a consolidated earnings statement meeting the requirements of Rule 158 under the Securities Act (which need not be audited) for the twelve-month period commencing after the effective date of the Shelf Registration Statement.

(b) Restrictions on Holders. Each Holder agrees that, upon receipt of the notice referred to in Section 3(a)(iii)(C) or any notice from the Company of the existence of any fact of the kind described in Section 3(a)(iii)(D) hereof (in each case, a “Suspension Notice”), such Holder will forthwith discontinue disposition of Registrable Securities pursuant to the Shelf Registration Statement until (i) such Holder’s receipt of the copies of the supplemented or amended Prospectus contemplated by Section 3(a)(xiii) hereof, or (ii) it is advised in writing by the Company that the use of the Prospectus may be resumed, and has received copies of any additional or supplemental filings that are incorporated by reference in the Prospectus. Each Holder receiving a Suspension Notice hereby agrees that it will either (1) destroy any Prospectuses, other than permanent file copies, then in such Holder’s possession which have been replaced by the Company with more recently dated Prospectuses, or (2) deliver to the Company (at the Company’s expense) all copies, other than permanent file copies then in such Holder’s possession, of the Prospectus covering such Registrable Securities that was current at the time of receipt of such notice. In the event the Company shall give any such notice, the time period regarding the effectiveness of such Shelf Registration Statement set forth in Section 2 hereof shall be extended by the number of days during the period from and including the date of the giving of such notice pursuant to Section 3(a)(iii)(D) hereof to and including the date when each selling Holder covered by such Shelf Registration Statement shall have received the copies of the supplemented or amended Prospectus contemplated by Section 3(a)(xiii) hereof or shall have been advised in writing that the use of the Prospectus may be resumed.

Section 4. Registration Expenses.

(a) All expenses incident to the Company’s performance of or compliance with this Agreement will be borne by the Company regardless of whether a Shelf Registration Statement becomes effective, including, without limitation: (i) all registration and filing fees and expenses (including filings made by any Holder with FINRA (and, if applicable, the fees and expenses of any “qualified independent underwriter” and its counsel that may be required by the rules and regulations of FINRA)); (ii) all fees and expenses of compliance with federal securities and state securities or blue sky laws; (iii) all fees and disbursements of counsel for the Company and reasonable and documented fees and disbursements for one counsel for all of the Holders of Registrable Securities; and (iv) all fees and disbursements of independent certified public accountants of the Company and the Guarantors (including the expenses of any special audit and comfort letters required by or incident to such performance).

8

The Company will, in any event, bear its internal expenses (including, without limitation, all salaries and expenses of its officers and employees performing legal or accounting duties), the expenses of any annual audit and the fees and expenses of any Person, including special experts, retained by the Company.

(b) In connection with a Shelf Registration Statement required by this Agreement, the Company will reimburse the Holders of Registrable Securities being registered pursuant to the Shelf Registration Statement for the reasonable and documented fees and disbursements of counsel.

Section 5. Indemnification.

(a) The Company agrees to indemnify and hold harmless (i) each Holder and (ii) each Person, if any, who controls (within the meaning of Section 15 of the Securities Act or Section 20 of the Exchange Act) any Holder (any of the Persons referred to in this clause (ii) being hereinafter referred to as a “controlling person”) and (iii) the respective officers, directors, partners, employees, representatives and agents of any Holder or any controlling person (any Person referred to in clause (i), (ii) or (iii) may hereinafter be referred to as an “Indemnified Holder”), to the fullest extent lawful, from and against any and all losses, claims, damages, liabilities, judgments, actions and expenses (including, without limitation, and as incurred, reimbursement of all reasonable out-of-pocket costs of investigating, preparing, pursuing, settling, compromising, paying or defending any claim or action, or any investigation or proceeding by any governmental agency or body, commenced or threatened, including the reasonable fees and expenses of counsel to any Indemnified Holder), joint or several, directly or indirectly caused by, related to, based upon, arising out of or in connection with any untrue statement or alleged untrue statement of a material fact contained in a Shelf Registration Statement or Prospectus (or any amendment or supplement thereto), or any omission or alleged omission to state therein a material fact required to be stated therein or necessary to make the statements therein not misleading, except insofar as such losses, claims, damages, liabilities or expenses are caused by an untrue statement or omission or alleged untrue statement or omission that is based upon information relating to any of the Holders furnished in writing to the Company by or on behalf of any of the Holders expressly for use therein or out of sales of Registrable Securities made during a Suspension Period after notice is given pursuant to Section 3(b) hereof. This indemnity agreement shall be in addition to any liability which the Company may otherwise have.

In case any action or proceeding (including any governmental or regulatory investigation or proceeding) shall be brought or asserted against any of the Indemnified Holders with respect to which indemnity may be sought against the Company, such Indemnified Holder (or the Indemnified Holder controlled by such controlling person) shall promptly notify the Company in writing; provided, however, that the failure to give such notice shall not relieve the Company of its obligations pursuant to this Agreement except to the extent that it had been materially prejudiced by such failure (through forfeiture of substantive rights). Such Indemnified Holder shall have the right to employ its own counsel in any such action and the

9

fees and expenses of such counsel shall be paid, as incurred, by the Company. The Company shall not, in connection with any one such action or proceeding or separate but substantially similar or related actions or proceedings in the same jurisdiction arising out of the same general allegations or circumstances, be liable for the reasonable fees and expenses of more than one separate firm of attorneys (in addition to any local counsel) at any time for such Indemnified Holders, which firm shall be designated by the Holders. The Company shall be liable for any settlement of any such action or proceeding effected with the Company’s prior written consent, which consent shall not be withheld unreasonably, and the Company agrees to indemnify and hold harmless any Indemnified Holder from and against any loss, claim, damage, liability or reasonable out-of-pocket expense by reason of any settlement of any action effected with the written consent of the Company. The Company shall not, without the prior written consent of each Indemnified Holder, settle or compromise or consent to the entry of judgment in or otherwise seek to terminate any pending or threatened action, claim, litigation or proceeding in respect of which indemnification or contribution may be sought hereunder (whether or not any Indemnified Holder is a party thereto), unless such settlement, compromise, consent or termination (i) includes an unconditional release of each Indemnified Holder from all liability arising out of such action, claim, litigation or proceeding and (ii) does not include a statement as to an admission of fault, culpability or a failure to act, by or on behalf of the Indemnified Holder.

(b) By its acquisition of Registrable Securities, each Holder of Registrable Securities agrees, severally and not jointly, to indemnify and hold harmless the Company and the directors and officers of the Company who sign a Shelf Registration Statement, and any Person controlling (within the meaning of Section 15 of the Securities Act or Section 20 of the Exchange Act) the Company, and the respective officers, directors, partners, employees, representatives and agents of each such Person, to the same extent as the foregoing indemnity from the Company to each of the Indemnified Holders, but only with respect to claims and actions based on information relating to such Holder furnished in writing by such Holder expressly for use in a Shelf Registration Statement. In case any action or proceeding shall be brought against the Company or its directors or officers or any such controlling person in respect of which indemnity may be sought against a Holder of Registrable Securities, such Holder shall have the rights and duties given the Company, and the Company, its directors and officers and such controlling person shall have the rights and duties given to each Holder by the preceding paragraph.

(c) If the indemnification provided for in this Section 5 is unavailable to an indemnified party under Section 5(a) or (b) hereof (other than by reason of exceptions provided in those Sections) in respect of any losses, claims, damages, liabilities, judgments, actions or expenses referred to therein, then each applicable indemnifying party, in lieu of indemnifying such indemnified party, shall contribute to the amount paid or payable by such indemnified party as a result of such losses, claims, damages, liabilities or expenses in such proportion as is appropriate to reflect the relative fault of the Company, on the one hand, and the Holders, on the other hand, in connection with the statements or omissions which resulted in such losses, claims, damages, liabilities or expenses, as well as any other relevant equitable considerations. The relative fault of the Company, on the one hand, and of the Indemnified Holder, on the other hand, shall be determined by reference to, among other things, whether the untrue or alleged untrue statement of a material fact or the omission or alleged omission to state a material fact relates to information supplied by the Company, on the one hand, or the Indemnified Holders, on

10

the other hand, and the parties’ relative intent, knowledge, access to information and opportunity to correct or prevent such statement or omission. The amount paid or payable by a party as a result of the losses, claims, damages, liabilities and expenses referred to above shall be deemed to include, subject to the limitations set forth in the second paragraph of Section 5(a) hereof, any legal or other fees or expenses reasonably incurred by such party in connection with investigating or defending any action or claim.

The Company and each Holder of Registrable Securities agree that it would not be just and equitable if contribution pursuant to this Section 5(c) were determined by pro rata allocation (even if the Holders were treated as one entity for such purpose) or by any other method of allocation which does not take account of the equitable considerations referred to in the immediately preceding paragraph. The amount paid or payable by an indemnified party as a result of the losses, claims, damages, liabilities or expenses referred to in the immediately preceding paragraph shall be deemed to include, subject to the limitations set forth above, any legal or other expenses reasonably incurred by such indemnified party in connection with investigating or defending any such action or claim. Notwithstanding the provisions of this Section 5, the total amount to be contributed by a Holder pursuant to this Section 5 shall be limited to the net proceeds (after deducting underwriters’ discounts and commissions) received by such Holder in the offering to which such Shelf Registration Statement or prospectus relates. No Person guilty of fraudulent misrepresentation (within the meaning of Section 11(f) of the Securities Act) shall be entitled to contribution from any Person who was not guilty of such fraudulent misrepresentation. The Holders’ obligations to contribute pursuant to this Section 5(c) are several in proportion to the respective principal amount of Securities held by each of the Holders hereunder and not joint.

Section 6. Underwritten Offerings. The Holders of Registrable Securities covered by the Shelf Registration Statement who desire to do so may sell such Registrable Securities in an underwritten offering. In any such underwritten offering, the investment banker(s) and managing underwriter(s) that will administer such offering will be selected by the Holders of a majority in aggregate principal amount of the Registrable Securities included in such offering; provided, however, that such investment banker(s) and managing underwriter(s) must be reasonably satisfactory to the Company. No Holder may participate in any underwritten offering hereunder unless such Holder (a) agrees to sell such Holder’s Registrable Securities on the basis provided in any underwriting arrangements approved by the Persons entitled hereunder to approve such arrangements and (b) completes and executes all reasonable questionnaires, powers of attorney, indemnities, underwriting agreements, lock-up letters and other documents required under the terms of such underwriting arrangements.

Section 7. Miscellaneous.

(a) Remedies. The Company hereby agrees that monetary damages would not be adequate compensation for any loss incurred by reason of a breach by it of the provisions of this Agreement and hereby agree to waive the defense in any action for specific performance that a remedy at law would be adequate.

(b) Assignment; No Third Party Beneficiaries; Additional Parties. This Agreement and the rights, duties and obligations of the Company and the Guarantors hereunder

11

may not be assigned or delegated by the Company or the Guarantors in whole or in part. This Agreement and the rights, duties and obligations of the Holders hereunder may be freely assigned or delegated by such Holder in conjunction with and to the extent of any transfer of Registrable Securities by any such Holder to a Permitted Transferee. This Agreement is not intended to confer any rights or benefits on any persons that are not party hereto other than as expressly set forth in Section 5 and this Section 7(b).

(c) No Inconsistent Agreements. The Company will not on or after the date of this Agreement enter into any agreement with respect to its securities that is inconsistent with the rights granted to the Holders in this Agreement or otherwise conflicts with the provisions hereof. The rights granted to the Holders hereunder do not in any way conflict with and are not inconsistent with the rights granted to the holders of the Company’s securities under any agreement in effect on the date hereof.

(d) Amendments and Waivers. The provisions of this Agreement may not be amended, modified or supplemented, and waivers or consents to or departures from the provisions hereof may not be given unless the Company has obtained the written consent of Holders of a majority of the outstanding principal amount of Registrable Securities (excluding any Registrable Securities held by the Company or its subsidiaries); provided, however, that, with respect to any matter that directly or indirectly affects the rights of any Initial Holder hereunder, the Company shall obtain the written consent of each such Initial Holder with respect to which such amendment, qualification, supplement, waiver, consent or departure is to be effective.

(e) Notices. All notices and other communications provided for or permitted hereunder shall be made in writing by hand-delivery, first-class mail (registered or certified, return receipt requested), telex, telecopier, or air courier guaranteeing overnight delivery:

(i) if to a Holder, at the address set forth on the records of the registrar under the indenture governing the New Notes; and

(ii) if to the Company:

Horizon Lines, Inc.

4064 Colony Road, Suite 200

Charlotte, NC 28211

Telephone: (704)  ###-###-####

Facsimile: (704)  ###-###-####

Attention: General Counsel

All such notices and communications shall be deemed to have been duly given: at the time delivered by hand, if personally delivered; five Business Days after being deposited in the mail, postage prepaid, if mailed; when answered back, if telexed; when receipt acknowledged, if telecopied; and on the next Business Day, if timely delivered to an air courier guaranteeing overnight delivery.

(f) Successors and Assigns. This Agreement shall inure to the benefit of and be binding upon the successors and assigns of each of the parties, including, without limitation,

12

and without the need for an express assignment, subsequent Holders of Registrable Securities; provided, however, that this Agreement shall not inure to the benefit of or be binding upon a successor or assign of a Holder unless and to the extent such successor or assign acquired Registrable Securities from such Holder.

(g) Counterparts. This Agreement may be executed in any number of counterparts and by the parties hereto in separate counterparts, each of which when so executed shall be deemed to be an original and all of which taken together shall constitute one and the same agreement.

(h) Headings. The headings in this Agreement are for convenience of reference only and shall not limit or otherwise affect the meaning hereof.

(i) Governing Law. This Agreement shall be governed by and construed in accordance with the laws of the State of New York, without regard to the conflicts of law rules thereof.

(j) Severability. In the event that any one or more of the provisions contained herein, or the application thereof in any circumstance, is held invalid, illegal or unenforceable, the validity, legality and enforceability of any such provision in every other respect and of the remaining provisions contained herein shall not be affected or impaired thereby.

(k) Entire Agreement. This Agreement is intended by the parties as a final expression of their agreement and intended to be a complete and exclusive statement of the agreement and understanding of the parties hereto in respect of the subject matter contained herein. There are no restrictions, promises, warranties or undertakings, other than those set forth or referred to herein with respect to the registration rights granted by the Company with respect to the Registrable Securities. This Agreement supersedes all prior agreements and understandings between the parties with respect to such subject matter.

(l) Use of Free Writing Prospectus. No Holder shall use a free writing prospectus prepared by or on behalf of the relevant Holder or used or referred to by such Holder in connection with the offering of Registrable Securities pursuant to the Shelf Registration Statement without the prior written consent of the Company, which shall not be unreasonably withheld.

13

IN WITNESS WHEREOF, the parties have executed this Agreement as of the date first written above.

The foregoing Registration Rights Agreement is hereby confirmed and accepted as of the date first above written: