INTEREST AND L/C LIABILITY AGREEMENT

Exhibit 10.4

INTEREST AND L/C LIABILITY AGREEMENT

THIS INTEREST AND L/C LIABILITY AGREEMENT, dated April 10, 2006 (this “Agreement”), is among HORIZON LINES, LLC., a Delaware limited liability company (“HLL”), SHIP FINANCE INTERNATIONAL LIMITED., a Bermuda company (the “SFL”), and FORTIS CAPITAL CORP., as Security Trustee (the “Security Trustee”) for the Lenders and the Swap Providers. Capitalized terms used but not defined herein shall have the meaning assigned such terms in the Credit Agreement (as defined below).

WHEREAS:

1. By a Credit Agreement dated as of April 7, 2006 (as the same may be amended or supplemented from time to time, the “Credit Agreement”), among HL Eagle LLC, HL Falcon LLC, HL Hawk LLC, HL Hunter LLC and HL Tiger LLC as joint and several borrowers (together, the “Borrowers”), the banks and financial institutions described therein as Lenders (the “Lenders”), Fortis Capital Corp. as Sole Book Runner, Lead Arranger, Agent and Security Trustee, The Governor and Company of the Bank of Scotland and NIBC Bank N.V., as Co-Arrangers, and Fortis Bank NV/SA, New York Branch, HBOS Treasury Services plc and NIBC Bank N.V., as Swap Providers (the “Swap Providers”), the Lenders have agreed to make loans to the Borrowers in the aggregate principal amount of up to Two Hundred Ten Million United States Dollars (U.S.$210,000,000) upon and subject to the terms therein described (the “Loan”).

2. The loan facility includes a U.S.$38,000,000 sub-limit letter of credit facility which will be used to issue the Letters of Credit required to be issued during the Pre-Delivery Period to satisfy the security deposits that the Borrowers are required to post under the Memoranda of Agreement entered into with the Sellers for the sale and purchase of the Vessels.

3. Pursuant to Master Agreements on the 1992 ISDA Master Agreement (Multicurrency-Crossborder) form dated April 10, 2006 made between the Borrowers and the Swap Providers, the Borrowers intend to enter into certain Transactions (as such term is defined in the said Master Agreements) pursuant to separate Confirmations providing for, amongst other things, the payment of certain amounts by the Borrowers to the Swap Providers in connection with the interest payable on the Loan.

4. Pursuant to an Interest Guarantee dated the date hereof (the “Interest Guarantee”) made by SFL in favor of the Security Trustee, SFL has guaranteed the Borrowers’ liability under the Master Agreements to the Swap Providers during the Pre-Delivery Period upon the terms and conditions stated therein.

5. Pursuant to a L/C Guarantee dated the date hereof (the “L/C Guarantee”, and together with the Interest Guarantee, the “SFL Guarantees”) made by SFL in favor of the Security Trustee, SFL has guaranteed the Borrowers’ liability to the Issuing Lender and the Letter of Credit Participants during the Pre-Delivery Period for the issuance of, and in respect of any drawings under, the Letters of Credit upon the terms and conditions stated therein.

6. Pursuant to a Reimbursement Agreement dated the date hereof (the “Reimbursement Agreement”) between HLL, SFL Holdings LLC (“SFL Holdings”) and the Borrowers, HLL has agreed to reimburse SFL Holdings and the Borrowers for certain liabilities upon the terms and conditions stated therein.

7. Pursuant to an Assignment of Reimbursement Agreement dated the date hereof (the “Reimbursement Agreement Assignment”), SFL Holdings and the Borrowers have assigned their rights under the Reimbursement Agreement to the Security Trustee, for the benefit of the Lenders and the Swap Providers, as security for the Borrowers’ obligations under the Loan Documents.

8. Pursuant to a Consent and Agreement dated the date hereof HLL consented to the Reimbursement Agreement Assignment.

9. HLL is providing to the Security Trustee eight (8) letters of credit (each, a “Back-up L/C” and collectively, the “Back-Up L/Cs”) issued pursuant to HLL’s senior credit facility, in the aggregate amount of $29,337,500; three of such letters of credit shall each be in the amount of $8,512,500 and shall each support HLL’s obligation under the Reimbursement Agreement to reimburse the relevant Borrower in respect of such Borrower’s liability under the Credit Agreement for amounts drawn by the beneficiary thereof under a Letter of Credit issued under the Credit Agreement (a “L/C Draw”); and five of such letters of credit shall each be in the amount of $760,000 and shall support HLL’s obligation under the Reimbursement Agreement to reimburse the relevant Borrower in respect of such Borrower’s liability under the Mater Agreements for a Delivery Failure (as defined in the Master Agreements) (a “Swap Breakage”).

10. The parties hereto desire to set forth the terms and conditions upon which the Security Trustee will exercise its rights under the SFL Guarantees and the Reimbursement Agreement, as assigned to it under the Reimbursement Agreement Assignment.

NOW, THEREFORE, in consideration of the premises and other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties hereby agree as follows:

Section 1. Event of Default. (a) At any time during the Pre-Delivery Period, upon either one (or more) L/C Draw(s) and/or one (or more) Swap Breakage(s), the Security Trustee shall make written demand upon SFL for payment under the SFL Guarantees in an amount equal to, as reasonably calculated by the Security Trustee, the sum of (i) the aggregate amount of such L/C Draw(s), (ii) the aggregate amount due for Swap Breakage(s), and (iii) any other amounts due in connection therewith under the Credit Agreement or the Master Agreements with respect to the Vessel or Vessels giving rise to the event(s) that result in such L/C Draw(s) and Swap Breakage(s) but excluding any amounts due under the Credit Agreement or the Master Agreements with respect to any other Vessel (the “Liability Amount”). The written demand shall set forth in reasonable detail the basis for and the calculation of the Liability Amount and shall be conclusive and binding for all purposes, absent manifest error.

(b) Within two (2) Business Days following its receipt of written demand by the Security Trustee, SFL shall either (i) pay the Security Trustee the Liability Amount or (ii) notify the Security Trustee that, in the reasonable opinion of SFL, the event(s) giving rise to the L/C Draw(s) and/or Swap Breakage(s) did not result from an Event of SFL Default having occurred under the Agreement to Acquire and Charter dated the date hereof (the “Agreement to Acquire and Charter”) among SFL, SFL Holdings, the Borrower and Horizon Lines, LLC, and that SFL is not liable for the Liability Amount. The Security Trustee shall have no obligation or duty to ascertain whether an Event of SFL Default has in fact occurred.

2

(c) In the event that SFL gives the Security Trustee the notice described in Section 1(b)(ii), the Security Trustee shall make written demand upon HLL under the Reimbursement Agreement for payment of the Liability Amount. The written demand shall set forth in reasonable detail the basis for and the calculation of the Liability Amount and shall be conclusive and binding for all purposes, absent manifest error.

(d) Within two (2) Business Days following its receipt of written demand by the Security Trustee, HLL shall either (i) reimburse the Security Trustee under the Reimbursement Agreement for such L/C Draw(s) and/or Swap Breakage(s) in an amount equal to the Liability Amount by the Security Trustee drawing upon the Back-Up L/C(s) related to the relevant Vessel(s) in an amount equal to the Liability Amount or (ii) notify the Security Trustee that, in the reasonable opinion of HLL, the event(s) giving rise to the L/C Draw(s) or Swap Breakage(s) did not result from an Event of HLL Default having occurred under the Agreement to Acquire and Charter and that HLL is not liable for the Liability Amount. The Security Trustee shall have no obligation or duty to ascertain whether an Event of HLL Default has in fact occurred.

(e) In the event that HLL gives the Security Trustee the notice described in Section 1(d)(ii), the parties agree that a deemed dispute (a “Deemed Dispute”) shall have occurred.

Section 2. Deemed Dispute. (a) Upon the occurrence of a Deemed Dispute, the Security Trustee shall notify each of SFL and HLL thereof and, within two (2) Business Days of the date of such notice, the Security Trustee shall draw upon the Back-Up L/Cs related to the relevant Vessel(s) in an amount equal 50% of the Liability Amount and SFL shall pay the Security Trustee an amount equal to 50% of the Liability Amount. Such payment by SFL shall be by wire transfer and in immediately available funds to the Agent’s Account at JPMorgan Chase Bank, New York, New York, ABA #021000021, Account Number 001-1-624418, Ref.: SFL/Horizon, free and clear of and without deduction for any and all present or future taxes, levies, imposts, deductions, charges or withholdings, and all liabilities with respect thereto. Each such payment shall be irrevocable and unconditional.

(b) Notwithstanding any provision of any Loan Document or other document to which any of the parties hereto are a party, (i) each of SFL and HLL hereby irrevocably waives any right to assert, enforce, or otherwise exercise any right of subrogation to any of the rights, security interests, claims, or liens which the Security Trustee, the Agent, any Lender or the Swap Providers may have against any Person in respect of the Liability Amount, (ii) each of SFL and HLL shall not have any right of recourse, reimbursement, contribution, indemnification, or similar right (by contract or otherwise) against the Security Trustee, the Agent, any Lender or the Swap Providers in respect of the Liability Amount, and (iii) each of SFL and HLL hereby irrevocably waives any and all of the foregoing rights and also irrevocably waives the benefit of, and any right to participate in, any Collateral or other security given to the Security Trustee, the Agent, any Lender or the Swap Providers to secure payment of the Liability Amount.

Section 3. Return of Back-Up L/Cs. (a) The Security Trustee shall return to HLL each Back-up L/C relating to a Vessel that has been delivered to and accepted by SFL Holdings under the relevant Memorandum of Agreement for such Vessel undrawn on the date of such delivery and acceptance promptly upon the return of the corresponding Letter of Credit issued under the Credit Agreement in respect of such Memorandum of Agreement being returned undrawn to the Security Trustee.

3

(b) Following a Deemed Dispute, the Security Trustee shall return to HLL the related Back-up L/C to HLL promptly after 50% of the amount thereof has been drawn by the Security Trustee in accordance with Section 2(a) of this Agreement.

Section 4. Representations, Warranties and Covenants. Each of SFL and HLL hereby represents, warrants and covenants as follows:

(a) The execution, delivery and performance by it of this Agreement and the consummation of other transactions contemplated hereby, are within its power, have been duly authorized by all necessary company or corporate action, as the case may be, and do not (i) contravene its organizational documents, (ii) violate any applicable law, order, writ, judgment, injunction, decree, determination or award, (iii) conflict with or result in the breach of, or constitute a default under, any credit agreement, contract, indenture, mortgage, deed of trust, lease or other instrument binding on or affecting it or any of its properties, or (iv) result in or require the creation or imposition of any lien upon or with respect to any of its properties.

(b) It is not in violation of any such law, rule, regulation, order, writ, judgment, injunction, decree, determination or award or in breach of any such contract, credit agreement, indenture, mortgage, deed of trust, lease or other instrument where such violation or breach is reasonably likely to result in a Material Adverse Effect with respect to it.

(c) No authorization, approval, consent or other action by, and no notice to or filing with, any governmental authority or regulatory body or any other consent or approval of any other person is required for the due execution, delivery, recordation, filing or performance by it of its obligations this Agreement.

(d) This Agreement has been duly executed and delivered by the it and is the legal, valid and binding obligations of it, enforceable against it in accordance with its terms, subject to applicable bankruptcy, insolvency, reorganization, moratorium or similar laws affecting the enforceability of creditors’ rights generally (regardless of whether enforcement is sought in equity or at law).

Section 5. Amendment. None of the terms or provisions of this Agreement may be waived, altered, modified or amended except by an instrument in writing, duly executed by all of the parties hereto.

Section 6. Notices. All notices and other communications provided for hereunder shall be in writing (including telecopier, telegraphic, telex communication) and overnight couriered, telecopied, telegraphed, telexed, or delivered:

(a) if to SFL, at 14 Par-la-Ville Road, Hamilton HM 08 Bermuda (Telefacsimile: 441 ###-###-####);

(b) if to HLL, at 4064 Colony Road, Suite 200, Charlotte, North Carolina 28211, Attention: Chief Financial Officer, (Telefacsimile: 704 ###-###-####); and

(c) if to the Security Trustee, at 520 Madison Avenue, New York, New York 10022, Attention: Loan Syndication/Agency (Telefacsimile: 212 ###-###-####).

4

or at such other address as shall be designated by such party in a written notice to the other parties. All such notices and communications shall be effective when received, if overnight couriered or delivered or telecopied (including machine acknowledgment).

Section 7. Governing Law; Jurisdiction; Waiver of Jury Trial.

(a) THIS AGREEMENT SHALL BE GOVERNED BY, AND CONSTRUED IN ACCORDANCE WITH, THE LAWS OF THE STATE OF NEW YORK.

(b) Each of the parties hereto hereby irrevocably submits to the jurisdiction of any New York State or Federal court sitting in New York County and any appellate court from any thereof in any action or proceeding arising out of or relating to this Agreement, and each of the parties hereto hereby irrevocably agrees that all claims in respect of any such action or proceeding may be heard and determined in such New York State or in such Federal court. Each of the parties hereto hereby irrevocably waives, to the fullest extent that it may effectively do so, any objection it may now or hereafter have to the laying of the venue of any action or proceeding arising out of or relating to this Agreement and the defense of an inconvenient forum to the maintenance of any such action or proceeding. Each of the parties hereto also irrevocably consents to the service of any and all process in any such action or proceeding by the mailing of copies of such process to it at its address specified in Section 4 above. Each of the parties hereto agrees that a final judgment in any such action or proceeding shall be conclusive and may be enforced in other jurisdictions by suit on the judgment or in any other manner provided by law.

Nothing in this Section 7(b) shall (i) affect the right of the Security Trustee to serve legal process in any other manner permitted by law or the right of the Security Trustee to bring any action or proceeding against SFL or HLL or their respective properties in the courts of any other jurisdictions where such action or proceeding may be heard or (ii) exclude or limit any right the Security Trustee may have (whether under the law of any country, an international convention or otherwise) with regard to the bringing of proceedings, the service of process, the recognition or enforcement of a judgment or any similar or related matter in any jurisdiction.

(c) EACH OF THE PARTIES WAIVES ANY AND ALL RIGHT TO TRIAL BY JURY IN ANY LEGAL ACTION OR PROCEEDING ARISING OUT OF OR RELATING TO THIS AGREEMENT OR THE TRANSACTIONS CONTEMPLATED HEREBY.

[THE REMAINDER OF THIS PAGE INTENTIONALLY LEFT BLANK]

5

IN WITNESS WHEREOF, each of the parties has duly executed and delivered this Agreement on the day and year first above written.

6