HORIZON LINES, LLC

Exhibit 10.36

Contract No. MA/CCF-607

CAPITAL CONSTRUCTION FUND AGREEMENT

WITH

HORIZON LINES, LLC

This CAPITAL CONSTRUCTION FUND AGREEMENT (the “Agreement”), entered into as of the 29^th day of March, 2004, by and between the UNITED STATES OF AMERICA, represented by the Secretary of Transportation, acting by and through the Maritime Administrator, (the “Maritime Administrator”) and HORIZON LINES, LLC, a company duly organized and existing under the laws of the State of Delaware (the “Party”), a citizen of the United States of America.

WHEREAS:

1. The Party has applied for the establishment of a Capital Construction Fund (the “Fund”) under Section 607 of the Merchant Marine Act, 1936, as amended (the “Act”);

2. The Party is the owner or lessee or has contracted for the construction of one or more “Eligible Vessels” as defined in Section 607(k) of the Act, which vessels are listed in Schedule A hereof;

3. The Party has a program for the construction or acquisition of “Qualified Agreement Vessels” as defined in Section 607(k) of the Act, which program is described in Schedule B hereof;

4. The Maritime Administrator and the Party desire to enter into an Agreement for the purpose of providing replacement vessels, additional vessels, or reconstructed vessels, built in the

United States and documented under the laws of the United States for operation in the United States foreign, Great Lakes, or noncontiguous domestic trade;

5. The Maritime Administrator has determined that the Party qualifies for an Agreement under the Act and the “Rules and Regulations” as hereinafter defined; and

6. The Maritime Administrator has authorized the award of an Agreement upon the terms and conditions set forth herein subject to the Act, as it may be amended from time to time, and such rules and regulations as are now or shall from time to time be prescribed by the Secretary of Transportation and/or his delegate, either alone or jointly with the Secretary of the Treasury, as necessary to carry out the powers, duties, and functions vested in them by the Act (the “Rules and Regulations”).

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

(A) A Fund is hereby established for the purposes set forth in Article 2 hereof, pursuant to the terms and conditions prescribed in this Agreement, the Act, and the Rules and Regulations.

(B) The Fund shall be established in one or more of the depositories listed in Schedule C hereof.

2

The Fund established hereunder shall be utilized to provide for replacement vessels, additional vessels, or reconstructed vessels, built in the United States and documented under the laws of the United States for operation in the United States foreign, Great Lakes, or noncontiguous domestic trade, and to provide for “Qualified Withdrawals” as defined in Section 607(f) of the Act, to accomplish the program set forth in Schedule B hereof.

This Agreement shall continue until terminated under Article 4.

(A) This Agreement may be terminated at any time under any of the following circumstances:

(1) Upon written mutual agreement by the parties;

(2) Upon written notice by the Party that a change has been made in the Rules and Regulations which would have a substantial effect upon the rights or obligations of the Party.

(B) This Agreement shall terminate upon completion of the program as set forth in Schedule B, unless otherwise mutually agreed by the parties.

(C) Upon termination of this Agreement pursuant to paragraphs (A) and/or (B) hereof all amounts remaining in the Fund shall be treated as if withdrawn in a “Non-qualified Withdrawal” as defined in Section 607(h) of the Act as of the date of termination of this Agreement.

3

(A) Subject to any restrictions contained in the Act, the Rules and Regulations, or this Agreement, the Party may deposit, for each taxable year to which this Agreement applies, amounts representing:

(1) Taxable income attributable to the operation of the vessels listed in Schedule A or B hereof;

(2) The depreciation allowable under Section 167 of the Internal Revenue Code of 1986 on the vessels listed in Schedule A or B hereof;

(3) The net proceeds from the sale or other disposition of any of the vessels listed in Schedule A or B hereof; and

(4) The net proceeds from insurance or indemnity attributable to the vessels listed in Schedule A or B hereof.

(B) The Party shall deposit for each taxable year to which this Agreement applies amounts representing:

(1) All receipts from the investment or reinvestment of amounts held in the Fund, except that the Party shall not be permitted to deposit more than is necessary to complete its program set out in Schedule B hereof; and

(2) The net proceeds from the mortgage of any vessel listed in Schedule B hereof for which qualified withdrawals from the Funds have been made.

4

(C) Notwithstanding any provision or provisions of sub. (A) or (B) of the paragraph 5, to the contrary, the Party shall make the minimum deposits set forth in Schedule D hereof at the time and in such amounts as any be set forth therein. The Party specifically agrees to deposit up to one hundred percent of allowable taxable income attributable to the operation of agreement vessels in order to meet its obligations under this paragraph.

(D) In the event that any leased vessel listed in Schedule A hereof is included in another capital construction fund agreement, the maximum amount of depreciation which the Party may deposit in respect to that vessel shall be calculated by using the allowable percentage of the depreciation ceiling listed for that vessel in Schedule A hereof.

(A) Except as otherwise required by the rules and regulations the Party may make such qualified withdrawals as shall be necessary to fulfill the obligations set forth in Schedule B hereof without the consent of the Maritime Administrator.

(B) Any other withdrawal from the Fund shall be made only upon the prior written consent of the Maritime Administrator.

(A) The Party, as its discretion, may invest assets held in the Fund in accordance with the Act and the Rules and Regulations.

5

(B) The Party agrees, when investing assets held in the Fund, to make such investments as will insure that sufficient cash is available at the time qualified withdrawals are required in accordance with the program described in Schedule B hereof.

(A) The Party agrees not to assign, pledge, or otherwise encumber, either directly or indirectly or through any reorganization, merger, or consolidation, all or any part of this Agreement, the Fund, or any assets in the Fund without the prior written consent of the Maritime Administrator; provided, however, the Party may transfer the assets of the Fund, in whole or in part, to an investment trustee, as provided in the rules and regulations.

(B) The Party shall not obligate any assets in the Fund as a compensating balance.

(C) The Party may not sell, transfer, or otherwise dispose of any vessel, or part thereof, described in Schedule B hereof without the prior written consent of the Maritime Administrator.

(A) The Party and each affiliate, domestic agents, subsidiary, or holding company connected with, or directly or indirectly controlling or controlled by the Party shall keep its books, records, and accounts relating to the maintenance, operation, and servicing of the vessel(s) and/or service(s) covered by this Agreement in such from as may be prescribed by the Maritime Administrator under the Rules and Regulations.

(B) The Maritime Administrator agrees not to require the duplication of book, records and accounts required to be kept in the some other form by the Interstate Commerce Commission or the

6

Secretary of the Treasury, so long as the information required in paragraph (A) hereof is made available to the Maritime Administrator.

(C) The Party agrees to file, upon notice from the Maritime Administrator, balance sheets, profit and loss statements, and such other statements of financial operations, special reports, charters, ships’ logs, memoranda of facts and transactions, as in the opinion of the Maritime Administrator may affect the Party’s performance under this Agreement.

(D) The Maritime Administrator may require by regulation that any of such statements, reports and memoranda shall be certified by independent certified public accountants acceptable to the Maritime Administrator.

(E) The Maritime Administrator may require the Party to establish and maintain systems of control of expenses and revenues in connection with the operation of the agreement vessel(s).

(F) The Party agrees to submit promptly to the Maritime Administrator any contract executed in connection with the program described in Schedule B hereof.

(G) The Maritime Administrator is hereby authorized to examine and audit the books, records, and accounts of all persons referred to in this Article whenever he may deem it necessary or desirable.

This Agreement may be modified or amended at any time by mutual written consent.

7

The attached Schedules A, B, C, and D are incorporated into and made a part of this Agreement.

(A) In the event that the Party operates any qualified agreement vessel described in Schedule B hereof in geographic trades other than those permitted by Section 607 of the Act, this Agreement, and/or the rules and regulations, the Party shall pay to the United States an amount of liquidated damages for each day of such impermissible geographic trading which shall constitute the time value of the deferral of Federal income tax which the Party has received. The amount shall be calculated in accordance with the rules and regulations.

(B) The Party agrees to pay the daily rate of liquidated damages to the Maritime Administrator, for deposit in the Treasury of the United States, within the time limits provided for in the rules and regulations.

(C) Nothing in this Article shall in any way be construed to diminish or waive any of the Maritime Administrator’s other remedies for breach under the Act, the Agreement, or the rules and regulations.

(D) Notwithstanding the fact that the Agreement may be terminated pursuant to the provisions of Article 4 hereof, or otherwise, the provisions of this Article 12 shall continue in effect as follows:

(1) In the case of a vessel constructed or acquired within one year of final delivery from the shipyard after construction and the aid of qualified withdrawals, for a period of twenty (20) years from the day of such vessel’s final delivery;

8

(2) In the case of a vessel reconstructed or acquired more than one year after final delivery from the shipyard after the construction with the aid of qualified withdrawals, for a period of ten (10) years from the date of such vessel’s final delivery from the shipyard after reconstruction or the date of such vessel’s acquisition; and

(3) In the case of a vessel included in Schedule B hereof as a qualified agreement vessel in regard to which qualified withdrawals from the Fund have been made to pay existing indebtedness, for a period of (10) years from the date of the first qualified withdrawal in regard to such vessel, provided, however, that if such vessel was more than fifteen (15) years old on the date of the first qualified withdrawal in regard thereto, such conditions shall continue for a period of five (5) years in regard to such vessel.

The Party hereby warrants and represents that:

(A) The Party is a citizen of the United States within the meaning of Section 2 of the Shipping Act, 1916, as amended, and will continue to be so for the term of this Agreement. The Party agrees that, each year, within thirty (30) days after the annual meeting of its stockholders, it shall file a supplemental affidavit as evidence of its continuing United States citizenship. In the event an annual stockholder’s meeting is not held or such meeting is not applicable to the Party, an affidavit shall be filed

9

on the anniversary date of the original filing. Provided, however, that any changes in the data last furnished by the Party which would result in a loss of the Party’s status as a United States citizen; i.e. changes in officers, directors, and stockholders; shall be promptly reported in writing to the Maritime Administration.

(B) The Party owns, is the lessee, or has contracted for the construction of one or more eligible vessels (within the meaning of Section 607(k) of the Act) as listed in Schedule A hereof.

(C) The qualified vessels described in Schedule B hereof:

(1) Were or will be constructed or reconstructed in the United States, except as provided in the Act and the rules and regulations;

(2) Are or will be documented under the laws of the United States and will continue to remain so documented; and

(3) Will be operated in the foreign, Great Lakes or noncontiguous domestic trade of the United States within the meaning of the Act and the Rules and Regulations.

(D) The Party will meet its deposit obligations as agreed upon in Article 5 of this Agreement.

(E) The Party will promptly inform the Maritime Administrator, in writing of any change in circumstances which would tend to adversely affect the ability of the Party to carry out its obligations under the Agreement.

(F) The Party will faithfully conform to all Rules and Regulations governing the Agreement and the Fund.

10

(G) Nothing of monetary value has been improperly given, promised, or implied for entering into this Agreement. The Party further warrants that no improper personal, political or other activities have been used or attempted in an effort to influence the outcome of the discussions or negotiations leading to the award of this Agreement. Breach of this warranty shall constitute an event of default for which the Maritime Administrator shall have the right, notwithstanding Article 4, to terminate this Agreement without liability to the United States.

(A) If the Maritime Administrator determines that any substantial obligation under this Agreement is not being fulfilled by the Party, he may, under the Rules and Regulations and after the Party has been given notice and an opportunity to be heard, declare a breach and treat the entire Fund, or any portion thereof, as an amount withdrawn in a nonqualified withdrawal.

(B) The Maritime Administrator shall provide an opportunity for the Party to cure a breach declared pursuant to Paragraph (A) of this Article 14.

( C) Events of breach by the Party shall include, but shall not be limited to:

(1) Failure in any respect to use due diligence in performing the program set forth in Schedule B hereof;

(2) Obligating the assets in the Fund as a compensating balance;

(3) Failure to make deposits required in Schedule D hereof;

(4) Failure to secure written permission from the Maritime Administrator when such permission is required by the rules and regulations;

11

(5) Failure to submit reports and/or records on a timely basis as provided in Article 9 hereof;

(6) Any material misrepresentation made by the Party or any failure by the Party to disclose material information in connection with this Agreement whether before or after execution hereof and whether made in an application, report, affidavit, or otherwise; or

(7) Failure by the Party to comply with any provisions of Section 607 of the Act, the Rules and Regulations, or this Agreement.

The Maritime Administrator agrees that the Federal income tax benefits provided in the Act and the Rules and Regulations shall be available to the Party if the Party shall carry out its obligations under this Agreement.

12

13