JOINDER NO. 1 TO ABL SECURITY AGREEMENT

Exhibit 10.4

JOINDER NO. 1 TO ABL SECURITY AGREEMENT

Joinder No. 1 (this “Joinder”), dated as of March 6, 2014 by and among Road Raiders Transportation, Inc., a Delaware corporation (the “New Subsidiary”), and WELLS FARGO CAPITAL FINANCE, LLC, in its capacity as agent for the Secured Party and the Bank Product Providers (in such capacity, together with its successors and assigns in such capacity, “Agent”).

W I T N E S S E T H:

WHEREAS, pursuant to that certain Credit Agreement dated as of October 5, 2011 (as amended, supplemented, extended, renewed, replaced, refunded, refinanced or otherwise modified from time to time, the “Credit Agreement”) by and among HORIZON LINES, INC., a Delaware corporation, as parent guarantor (“Parent”), HORIZON LINES, LLC, a Delaware limited liability company, as borrower (“Borrower”), the lenders party thereto as “Lenders” (such Lenders, together with their respective successors and assigns in such capacity, each, individually, a “Lender” and, collectively, the “Lenders”), and Agent, the Secured Party has agreed to make certain financial accommodations available to Borrower from time to time pursuant to the terms and conditions thereof; and

WHEREAS, pursuant to Section 5.11 of the Credit Agreement, the New Subsidiary is required to execute, among other documents, this Joinder in order to become a (a) Guarantor under the Guaranty; (b) Grantor under the Security Agreement; and (c) party to the Intercreditor Agreement; and

WHEREAS, the New Subsidiary (a) is a Subsidiary of the Parent and, as such, will benefit by virtue of the financial accommodations extended to the Borrower by the Secured Party and (b) by becoming a Loan Party will benefit from certain rights granted to the Loan Parties pursuant to the terms of the Loan Documents;

NOW, THEREFORE, for and in consideration of the foregoing and other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, each New Subsidiary hereby agrees as follows:

1. All initially capitalized terms used but not otherwise defined herein have the meanings given to them in the Security Agreement or, if not defined therein, in the Credit Agreement.

2. The New Subsidiary, by its signature below, becomes a “Grantor” under the Security Agreement with the same force and effect as if originally named therein as a “Grantor” and the New Subsidiary hereby (a) agrees to all of the terms and provisions of the Security Agreement applicable to it as a “Grantor” thereunder and (b) represents and warrants that the representations and warranties made by it as a “Grantor” thereunder are true and correct in all material respects (except that such materiality qualifier shall not be applicable to any representations and warranties that are already qualified or modified by materiality in the text thereof) on and as of the date hereof. In furtherance of the foregoing, the New Subsidiary does hereby unconditionally grant to Agent, for the benefit of the Secured Parties, to secure the Secured Obligations, a continuing security interest in and to all of such New Subsidiary’s right, title and interest in and to the Collateral. The Schedules attached hereto supplement each of the

respective Schedules to the Security Agreement. Each reference to a “Grantor” in the Security Agreement and the other Loan Documents shall be deemed to include the New Subsidiary. The Security Agreement is incorporated herein by reference. The New Subsidiary authorizes Agent at any time and from time to time to file, transmit, or communicate, as applicable, financing statements and amendments thereto (i) describing the Collateral as “all personal property of debtor” or “all assets of debtor” or words of similar effect, (ii) describing the Collateral as being of equal or lesser scope or with greater detail, or (iii) that contain any information required by part 5 of Article 9 of the Code for the sufficiency or filing office acceptance. The New Subsidiary also hereby ratifies any and all financing statements or amendments previously filed by Agent in any jurisdiction in connection with the Loan Documents.

3. The New Subsidiary, by its signature below, becomes a “Guarantor” under the Guaranty with the same force and effect as if originally named therein as a “Guarantor” and the New Subsidiary hereby (a) agrees to all of the terms and provisions of the Guaranty applicable to it as a “Guarantor” thereunder and (b) represents and warrants that the representations and warranties made by it as a “Guarantor” thereunder are true and correct in all material respects (except that such materiality qualifier shall not be applicable to any representations and warranties that are already qualified or modified by materiality in the text thereof) on and as of the date hereof. In furtherance of the foregoing, the New Subsidiary does hereby, jointly and severally together with the other Guarantors, guaranty to Agent, for the benefit of the Secured Party, as provided in the Guaranty, the prompt payment and performance of the Guarantied Obligations in full when due (whether at stated maturity, as a mandatory prepayment, by acceleration or otherwise) strictly in accordance with the terms thereof. Each reference to a “Guarantor”, the “Guarantors”, a “Guarantor” or the “Guarantors” in the Guaranty and the other Loan Documents shall be deemed to include the New Subsidiary. The Guaranty is incorporated herein by reference.

4. The New Subsidiary, by its signature below, becomes a party to the Intercreditor Agreement and the New Subsidiary hereby (a) agrees to all of the terms and provisions of Intercreditor Agreement applicable to it as a “Guarantor/Grantor” thereunder and (b) represents and warrants that the representations and warranties made by it as a “Guarantor/Grantor” thereunder are true and correct in all material respects (except that such materiality qualifier shall not be applicable to any representations and warranties that are already qualified or modified by materiality in the text thereof) on and as of the date hereof. Each reference to a “Guarantor/Grantor]” in the Intercreditor Agreement shall be deemed to include the New Subsidiary.

5. The New Subsidiary represents and warrants to Agent and the Secured Parties that this Joinder has been duly executed and delivered by such New Subsidiary and constitutes its legal, valid, and binding obligation, enforceable against it in accordance with its terms, except as enforceability thereof may be limited by bankruptcy, insolvency, reorganization, fraudulent transfer, moratorium, or other similar laws affecting creditors’ rights generally and general principles of equity (regardless of whether such enforceability is considered in a proceeding at law or in equity).

6. This Agreement is a Loan Document. This Agreement may be executed in any number of counterparts and by different parties on separate counterparts, each of which, when executed and delivered, shall be deemed to be an original, and all of which, when taken together, shall constitute but one and the same agreement. Delivery of an executed counterpart of this Joinder by telefacsimile or other electronic method of transmission shall be equally as effective as delivery of an original executed counterpart of this Joinder. Any party delivering an executed counterpart of this Joinder by telefacsimile or other electronic method of transmission also shall deliver an original executed counterpart of this Joinder but the failure to deliver an original executed counterpart shall not affect the validity, enforceability, and binding effect of this Joinder.

7. The Security Agreement, as supplemented hereby, shall remain in full force and effect.

8. THE VALIDITY OF THIS JOINDER, THE CONSTRUCTION, INTERPRETATION, AND ENFORCEMENT HEREOF, AND THE RIGHTS OF THE PARTIES HERETO WITH RESPECT TO ALL MATTERS ARISING HEREUNDER OR RELATED HERETO SHALL BE DETERMINED UNDER, GOVERNED BY, AND CONSTRUED IN ACCORDANCE WITH THE LAWS OF THE STATE OF NEW YORK.

9. THE PARTIES AGREE THAT ALL ACTIONS OR PROCEEDINGS ARISING IN CONNECTION WITH THIS JOINDER SHALL BE TRIED AND LITIGATED ONLY IN THE STATE AND, TO THE EXTENT PERMITTED BY APPLICABLE LAW, FEDERAL COURTS LOCATED IN THE COUNTY OF NEW YORK, STATE OF NEW YORK; PROVIDED, HOWEVER, THAT ANY SUIT SEEKING ENFORCEMENT AGAINST ANY COLLATERAL OR OTHER PROPERTY MAY BE BROUGHT, AT AGENT’S OPTION, IN THE COURTS OF ANY JURISDICTION WHERE AGENT ELECTS TO BRING SUCH ACTION OR WHERE SUCH COLLATERAL OR OTHER PROPERTY MAY BE FOUND. AGENT AND EACH NEW SUBSIDIARY WAIVE, TO THE EXTENT PERMITTED UNDER APPLICABLE LAW, ANY RIGHT EACH MAY HAVE TO ASSERT THE DOCTRINE OF FORUM NON CONVENIENS OR TO OBJECT TO VENUE TO THE EXTENT ANY PROCEEDING IS BROUGHT IN ACCORDANCE WITH THIS SECTION 9.

10. TO THE MAXIMUM EXTENT PERMITTED BY APPLICABLE LAW, AGENT AND EACH NEW SUBSIDIARY HEREBY WAIVE THEIR RESPECTIVE RIGHTS TO A JURY TRIAL OF ANY CLAIM OR CAUSE OF ACTION BASED UPON OR ARISING OUT OF THIS JOINDER OR ANY OF THE TRANSACTIONS CONTEMPLATED HEREIN, INCLUDING CONTRACT CLAIMS, TORT CLAIMS, BREACH OF DUTY CLAIMS, AND ALL OTHER COMMON LAW OR STATUTORY CLAIMS. AGENT AND EACH NEW SUBSIDIARY REPRESENT THAT EACH HAS REVIEWED THIS WAIVER AND EACH KNOWINGLY AND VOLUNTARILY WAIVES ITS JURY TRIAL RIGHTS FOLLOWING CONSULTATION WITH LEGAL COUNSEL. IN THE EVENT OF LITIGATION, A COPY OF THIS JOINDER MAY BE FILED AS A WRITTEN CONSENT TO A TRIAL BY THE COURT.

[REMAINDER OF THIS PAGE INTENTIONALLY LEFT BLANK]

IN WITNESS WHEREOF, the parties hereto have caused this Joinder to the Security Agreement to be executed and delivered as of the day and year first above written.