Exhibit 10.4

THIS FIRST AMENDMENT TO THE REGISTRATION RIGHTS AGREEMENTS (this “Amendment”) is made as of April 3, 2012, by and among Horizon Lines, LLC, a Delaware limited liability company (the “Company”), Horizon Lines, Inc. and its subsidiaries set forth on the signature page hereto (collectively, the “Guarantors”) and the Purchasers, governing each of the Company’s (i) 11.0% Senior Secured Notes due 2016 and (ii) Second Lien Senior Secured Notes due 2016. The Company, the Guarantors and the Purchasers are sometimes referred to herein individually as a “Party” and collectively as the “Parties”. Capitalized terms used herein but not defined herein shall have the meanings given to such terms in the Registration Rights Agreements (as herein defined).

WHEREAS:

(A) The Parties entered into that certain Registration Rights Agreement in relation to the First-Lien Notes (the “First-Lien Registration Rights Agreement”) dated as of October 5, 2011.

(B) The Parties entered into that certain Registration Rights Agreement in relation to the Second-Lien Notes (the “Second-Lien Registration Rights Agreement” and, together with the First-Lien Registration Rights Agreement, the “Registration Rights Agreements”) dated as of October 5, 2011.

(C) The Parties hereto desire to amend each of the Registration Rights Agreements as set forth in this Amendment.

NOW, THEREFORE, in consideration of the premises and the agreements, provisions and covenants herein contained, the Parties hereby agree as follows:

1. The second sentence of the first paragraph of Section 3.1(a) of each of the Registration Rights Agreements is hereby deleted in its entirety and replaced with the following:

“Each of the Company and the Guarantors shall use commercially reasonable efforts to Consummate the Exchange Offer as soon as practicable after the Closing Date, but in any event not later than 300 days following the Closing Date (such 300th day being the “Exchange Date”).”

2. This Amendment amends solely the provisions of the Registration Rights Agreements set forth herein and nothing in this Amendment is intended or shall be construed as amending or waiving any other terms or provisions of the Registration Rights Agreements or any other rights of the Parties under the Registration Rights Agreements. The Parties acknowledge that the Registration Rights Agreements (as amended by this Amendment) are in full force and effect and is hereby confirmed and ratified in all respects. References in each of the Registration Rights Agreements to the relevant Registration Rights Agreement shall mean the relevant Registration Rights Agreement as amended by this Amendment.

3. This Amendment may be executed in any number of counterparts (including by facsimile), each of which will be an original with the same effect as if the signatures thereto and hereto were upon the same instrument. This Amendment shall become effective when each Party shall have received counterparts hereof signed by all of the other Parties.

4. Each Purchaser that executes this Amendment hereby represents, with respect to itself only, that it holds the securities set forth on its signature page as of the date hereof.

5. THIS AMENDMENT 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.

[signature pages follow]

IN WITNESS WHEREOF, the parties have executed this First Amendment to the Registration Rights Agreements as of the date first written above.

[Signature Page to First Amendment to Registration Rights Agreements]

The foregoing First Amendment to the Registration Rights Agreements is hereby confirmed and accepted as of the date first above written:

$[            ] in aggregate principal amount of 11.00% First Lien Senior Secured Notes due 2016 issued by Horizon Lines, LLC

$[            ] in aggregate principal amount of Second Lien Senior Secured Notes due 2016 issued by Horizon Lines, LLC.

[Signature Page to First Amendment to Registration Rights Agreements]