HORIZON LINES HOLDING CORP. VOTING TRUST AGREEMENT

Exhibit 9.1

EXECUTION VERSION

HORIZON LINES HOLDING CORP.

Voting Trust Agreement, dated as of July 7, 2004 (this “Agreement”), among Horizon Lines Holding Corp. (“Horizon”), each of the persons listed on the signature pages hereto (the “Stockholders”) and ▇▇▇▇ ▇. ▇▇▇▇▇▇ and any successor appointed as provided in this Agreement, as Voting Trustee (the “Voting Trustee”).

Recitals:

Horizon is duly organized and validly existing under the laws of the State of Delaware, and, as of the date hereof, the Stockholders are the owners of options exercisable for the number of shares of the Common Stock, par value $.01 per share, of Horizon (such options, the “Options” and such shares, the “Common Stock”) as set forth opposite such Stockholder’s name on Exhibit A hereto (the shares of Common Stock that may be owned of record or beneficially now or in the future hereafter from time to time by the Stockholders being referred to herein collectively as “Shares”).

In consideration of the premises and of the mutual undertakings of the parties hereinafter set forth, a voting trust (the “Trust”) in respect of the Shares of Horizon that will be owned by the Stockholders is hereby created and established, subject to the following terms and conditions, to all and every one of which the parties hereto expressly assent and agree.

1. Deposit of Shares.

(a) Transfer of Shares. Each Stockholder agrees that, concurrently with the execution and delivery of this Agreement, he, she or it will transfer and assign, or cause to be transferred and assigned, to the Voting Trustee all of the Shares of Horizon now owned by him, her or it or which will be owned by him, her or it upon exercise of the Options and will deposit or cause to be deposited hereunder, with the Voting Trustee, the certificates for such Shares, all of which certificates, if not registered in the name of the Voting Trustee, shall be duly endorsed in blank or accompanied by proper instruments of assignment and transfer thereof duly executed in blank.

(b) All Capital Stock. The provisions of this Agreement shall apply to any and all Shares of Horizon that (i) may be issued in respect of, in exchange for, or in substitution of any Shares transferred to the Voting Trustee pursuant to Section 1(a) hereof, or (ii) are hereafter acquired by any Stockholder at any time, and each Stockholder agrees that until the termination of this Agreement no Shares of Horizon shall be held by such Stockholder, but all such Shares shall be deposited with the Voting Trustee in accordance with the terms and conditions of this Agreement.

2. Voting Trust Certificates.

(a) Issuance of Certificates. Subject to the provisions of Section 4 hereof, the Voting Trustee shall from time to time issue to each Stockholder, with respect to the

Shares of Horizon owned by such Stockholder and so deposited hereunder, a Voting Trust Certificate or Voting Trust Certificates, each in the form of Exhibit B, for the number of Shares equal to that deposited by such Stockholder, which Certificate or Certificates shall refer to the provisions of this Agreement and be registered on the books of the Trust in such Stockholder’s name.

(b) Transfer of Certificates. Voting Trust Certificates shall, to the extent permitted by law and the terms of this Agreement, be transferable (subject to the limitations on transfer otherwise applicable) in the same manner as negotiable instruments; provided, however, that ownership of such Voting Trust Certificates shall be transferable on the books of the Trust by the holders of record thereof only upon (i) the surrender of such Certificates, properly endorsed by the registered holders, and (ii) delivery to the Voting Trustee (A) by the proposed transferee, of a valid undertaking, in form and substance satisfactory to the Voting Trustee, to become, and such transferee becoming, bound by the terms of this Agreement, and (B) by the proposed transferor, of an opinion of counsel or no-action letter as provided in Section 4 hereof.

3. Stockholders Agreement.

(a) Limitations on Transfer. All Voting Trust Certificates issued hereunder shall be subject to the limitations on transfer and all other terms provided, with respect to the Shares now or hereafter transferred to the Voting Trustee hereunder, in the Stockholders Agreement dated as of the date hereof, among H-Lines Holdings Corp. (“Holdings”) and certain of holders of stock and/or options in Horizon and/or Holdings (the “Stockholders Agreement”), a copy of which is on file with Horizon.

(b) Notices. Any notice required to be given by any Stockholder to Horizon, Holdings or others under the Stockholders Agreement with respect to the purchase or sale of any Shares transferred hereunder shall be given to the Voting Trustee who shall promptly transmit such notice to Horizon, and Horizon shall thereafter give all notices required under such Stockholders Agreement to be given to others, including the other stockholders of Horizon and Holdings.

4. Non-Registration of Certificates. The Voting Trustee will not register the Voting Trust Certificates under the Securities Act of 1933, as amended (the “Securities Act”), or under the securities laws of any state in reliance upon each Stockholder’s representation hereby made that he, she or it will hold the Voting Trust Certificates subject to all applicable provisions of the Securities Act and such state laws and all applicable rules and regulations promulgated thereunder, and will not offer, sell, transfer or otherwise dispose of said Voting Trust Certificates or any part thereof unless (in addition to compliance with any other applicable restrictions on transfer) he, she or it shall have first obtained (i) an opinion of counsel, in form and substance satisfactory to the Voting Trustee, to the effect that such disposition will not result in a violation of any federal or state law applicable to the offer and sale of securities, or (ii) written advice from the Securities and Exchange Commission that it will take no action with respect to any such proposed disposition of said Voting Trust Certificates.

5. Replacement of Certificates. In case any Voting Trust Certificate shall be mutilated, lost, destroyed or stolen, the Voting Trustee may issue and deliver in exchange

therefor and upon cancellation of the mutilated Voting Trust Certificate, or in lieu of the lost, destroyed or stolen Voting Trust Certificate, a new Voting Trust Certificate or Voting Trust Certificates representing a like number of Shares, upon the production of evidence of such loss, destruction or theft, satisfactory to the Voting Trustee, and upon receipt of an indemnity satisfactory to the Voting Trustee, and upon compliance also with such other reasonable conditions as the Voting Trustee may prescribe.

6. Stock Certificates Held by Voting Trustees.

(a) Surrender of Certificates. The certificates for Shares of Horizon deposited with the Voting Trustee shall, if not registered in the name of the Voting Trustee, be surrendered to Horizon and canceled and new certificates therefor issued to and in the name of the Voting Trustee. Notation shall be made on the face of all certificates issued in the name of the Voting Trustee that they are issued pursuant to this Agreement, and such fact shall also be noted in the records of stock ownership of Horizon.

(b) Shares Held in Trust. All Shares deposited with the Voting Trustee hereunder shall be held in trust for the Stockholders and their respective heirs, executors, administrators and assigns, and used and applied by the Voting Trustee and his successors in office for the purposes of and in accordance with this Agreement and shall remain subject to the Stockholders Agreement.

(c) Transfer of Shares. The Voting Trustee may cause any Shares at any time held by him under this Agreement to be transferred to any name or names other than the name of the Voting Trustee herein named, if such transfer becomes necessary by reason of any change in the person holding the office of Voting Trustee as hereinafter provided.

7. Dividends; Stockholders Rights.

(a) Dividends. Horizon is hereby authorized and directed, and Horizon hereby agrees, to pay all distributions and dividends that become payable (and to which the holders of the capital stock shall be entitled) in cash, stock (other than stock entitled to vote in the selection of directors generally (the “Voting Stock”)) or other property directly to the registered holder of the Voting Trust Certificate evidencing the Shares on which such distributions, redemption payments or dividends are declared. All Voting Stock issued as dividends or otherwise in respect of the Shares shall also be subject to this Agreement. The stock certificates for such shares shall be issued in the name of and delivered to the Voting Trustee to be held hereunder, subject to all of the provisions hereof, and the Voting Trustee shall issue additional Voting Trust Certificates in respect of such shares to the Stockholders entitled thereto.

(b) Distributions of Capital Stock. In case Horizon shall at any time issue any stock or other securities to which the holders of Common Stock shall be entitled to subscribe by way of preemptive right or otherwise, or any Stockholder shall be otherwise entitled (including, without limitation, pursuant to the Stockholders Agreement) to purchase any shares of capital stock of Horizon, the Voting Trustee shall promptly give notice of such right so to subscribe or purchase and of the terms thereof to such Stockholder at his, her or its address

registered with the Voting Trustee; and such Stockholder upon providing the Voting Trustee with funds in the requisite amount, shall have the right, subject to such reasonable regulations as may be prescribed by the Voting Trustee, to instruct the Voting Trustee to subscribe for or purchase such stock or other securities, or any part thereof; and to the extent that such Stockholder shall fail to exercise such rights the Voting Trustee shall be entitled, in its absolute discretion, to permit such rights so to subscribe or purchase to lapse. Upon receiving proper instructions in writing, the Voting Trustee shall subscribe for or purchase such stock or other securities (but only out of funds provided by such Stockholder for the purpose) and shall distribute the same to such Stockholder, except that any shares of Voting Stock of Horizon, when so subscribed for or purchased and received by the Voting Trustee, shall not be distributed but shall be held hereunder, subject to all the provisions hereof, and the Voting Trustee shall issue new or additional Voting Trust Certificates in appropriate form in respect of such shares to such Stockholder.

8. Actions by Voting Trustee.

(a) Proxy. A proxy may be given to any person other than the Voting Trustee; provided, that such proxy may be voted only in accordance with specific instructions given by the Voting Trustee.

(b) Agents. The Voting Trustee may at any time or from time to time appoint an agent or agents and may delegate to such agent or agents the performance of any administrative duty of the Voting Trustee, including, without limitation, the appointment of a domestic bank or other institution to act as custodian of the Shares of Horizon held by it hereunder. The fees of such agent or agents shall constitute an expense of the Voting Trustee.

9. Liability of Voting Trustee; Indemnification.

(a) No Liability. The Voting Trustee assumes no liability as a stockholder, his interest hereunder being that of trustee only. In voting the stock represented by the stock certificates held by it hereunder (which he may do either in person or by proxy as aforesaid), the Voting Trustee will vote and act in all matters in accordance with his best good faith judgment and the terms of this Agreement, without taking into consideration the preferences of the Stockholders; but he assumes no responsibility or liability in respect of any action taken by him or taken in pursuance of his vote so cast, and the Voting Trustee shall not incur any responsibility as trustee or otherwise by reason of any error of fact or law, mistake of judgment, or of any matter or thing done or suffered or omitted to be done under this Agreement, except for his own individual gross negligence or willful misconduct.

(b) Agents. The Voting Trustee shall not be answerable for the default or misconduct of any agent or attorney appointed by him in pursuance hereof if such agent or attorney shall have been selected with reasonable care.

(c) Expenses. The Voting Trustee shall not be entitled to any compensation for his services but shall be reimbursed by the Stockholders for any reasonable expenses (other than counsel, advisors’ and agents’ fees) paid or incurred in the administration of the trust hereunder.

(d) Indemnity. The Stockholders hereby jointly and severally agree that they will at all times protect, indemnify and save harmless the Voting Trustee from any loss, cost or expense of any kind or character whatsoever incurred in connection with this Trust except those, if any, arising from the gross negligence or willful misconduct of the Voting Trustee, and will at all times themselves undertake, assume full responsibility for, and pay all costs and expenses of any suit or litigation of any character, including any proceedings before any governmental agency, with respect to the Shares or this Agreement and, if the Voting Trustee shall be made a party thereto, the Stockholders will pay all costs and expenses, including counsel fees, to which the Voting Trustee may be subject by reason thereof. The Voting Trustee may consult with counsel and other advisors, and the opinions of such counsel and advisors shall be full and complete authorization and protection in respect of any action taken or omitted or suffered by the Voting Trustee hereunder in good faith and in accordance with such opinions.

(e) Survival. Notwithstanding any other provision hereof, the provisions of this Section 9 shall survive the termination of this Agreement.

10. Voting Discretion.

(a) Voting Discretion. Except as otherwise provided herein, until the termination of this Agreement and the actual delivery of stock certificates in exchange for Voting Trust Certificates hereunder, the Voting Trustee shall possess and shall be entitled in his discretion, not subject to any review, to exercise in person or by proxy, in respect of any and all Shares at any time deposited under this Agreement, all rights and powers of every name and nature, including the right to vote thereon or to consent to any and every act of Horizon, in the same manner and to the same extent as if he were the absolute owner of such stock in his own right.

(b) Permitted Actions. Without limiting the generality of Section 10(a), the Voting Trustee is specifically authorized to vote for or consent to any of the following:

(i) (A) an increase or decrease in the authorized capital of Horizon; (B) the creation or authorization of any class of capital stock of Horizon; (C) the issuance or sale of any shares of capital stock or rights to acquire capital stock of Horizon or any subsidiary of Horizon (by conversion, exercise of a warrant or option or otherwise);

(ii) any amendment of the certificate of incorporation or by-laws of Horizon;

(iii) the incurrence of any indebtedness for borrowed money;

(iv) the appointment, election, termination or removal of any officer or director of Horizon;

(v) the declaration or payment of any dividend or other distribution to the stockholders of Horizon;

(vi) the sale or disposal in the normal course of business of any part or parts of the property, assets or business of Horizon.

(vii) (A) entering into any transaction of merger, consolidation or amalgamation, or liquidation, winding up or dissolution, (B) the conveyance, sale, lease, transfer or other disposition of, in a transaction or related series of transactions, substantially all of Horizon’s or any of its subsidiaries’ property, business or assets, (C) acquisition by purchase or otherwise of all of the capital stock or other evidences of beneficial ownership of Horizon or any of its subsidiaries, or (D) any recapitalization or similar restructuring transaction;

(viii) the acquisition, directly or indirectly, of a significant amount of assets other than in the ordinary course of business;

(ix) the sale or disposition of, directly or indirectly, a significant amount of assets other than in the ordinary course of business;

(x) adoption of any stock option plan for employees or any material changes in any such stock option plan or any other executive compensation plan of Horizon or any of its subsidiaries;

(xi) any change in the annual compensation of any officer of Horizon;

(xii) any loans to officers, managers or shareholders;

(xiii) any indemnification of officers, managers or agents of Horizon;

(xiv) any other extraordinary transaction, including any transaction that changes or would change the nature of the business of Horizon or its subsidiaries; and

(xv) any other proposal to be voted on or consented to by stockholders of Horizon.

11. Representations and Warranties of the Stockholders.

Each Stockholder hereby represents and warrants to the Voting Trustee as follows:

(a) Authority Relative to This Agreement. Such Stockholder has all requisite power and authority to enter into this Agreement and to perform its obligations hereunder. This Agreement has been duly authorized, executed and delivered by such Stockholder and, assuming this Agreement constitutes a valid and binding obligation of the other parties hereto, constitutes a legal, valid and binding obligation of such Stockholder, enforceable against such Stockholder in accordance with its terms, except to the extent that the enforceability thereof may be limited by: (i) applicable bankruptcy, insolvency, fraudulent conveyance, reorganization, moratorium or similar laws from time to time in effect affecting generally the

enforcement of creditors’ rights and remedies; and (ii) general principles of equity, including, without limitation, principles of reasonableness, good faith and fair dealing (regardless of whether enforcement is sought in equity or at law).

(b) No Conflict. (i) The execution and delivery of this Agreement by such Stockholder and performance of its obligations hereunder do not (A) conflict with or violate any laws applicable to such Stockholder or by which the Shares held by such Stockholder, or which will be held by such Stockholder upon exercise of his/her/its Options, are or will be bound or affected or (B) result in any breach of or constitute a default (or an event that with notice or lapse of time or both would become a default) under, or give to others any rights of termination, amendment, acceleration or cancellation of, or result in the creation of a lien or encumbrance on any of the Shares held by such Stockholder, or which will be held by such Stockholder upon exercise of his/her/its Options, pursuant to, any note, bond, mortgage, indenture, contract, lease, license, permit, franchise or other instrument or obligation to which such Stockholder is a party or by which such Stockholder or the Shares held by such Stockholder are or will be bound or affected.

(ii) The execution and delivery of this Agreement by such Stockholder do not, and the performance of this Agreement by such Stockholder will not, require any consent, authorization or approval or other action by, or notice to or filing with, any governmental authority or other person.

(c) Title to the Shares. As of the date hereof, such Stockholder is the record and beneficial owner of Options exercisable for the number of shares of Common Stock as set forth opposite such Stockholder’s name on Exhibit A hereto free and clear of all security interests, liens, claims, pledges, options, rights of first refusal, contracts, limitations on such Stockholder’s voting rights, charges and other encumbrances of any nature whatsoever, other than the Stockholders Agreement. Upon exercise of the Options, Stockholder will be the record and beneficial owner of the number of shares of Common Stock as set forth opposite such Stockholder’s name on Exhibit A hereto free and clear of all security interests, liens, claims, pledges, options, rights of first refusal, contracts, limitations on such Stockholder’s voting rights, charges and other encumbrances of any nature whatsoever, other than the Stockholders Agreement. Except as provided in this Agreement, such Stockholder has not appointed or granted (and will not, after the date hereof, appoint or grant) any proxy, which appointment or grant is still effective, with respect to the shares set forth opposite such Stockholder’s name on Exhibit A hereto.

12. Termination of this Agreement.

(a) Term. Unless terminated sooner pursuant to Section 12(b) hereof, this Agreement shall continue in effect for the maximum period permitted by applicable law as in effect on the date hereof.

(b) Termination. This Agreement shall terminate with respect to any Shares of Horizon sold, transferred or disposed of by any Stockholder as provided in and subject to compliance with the terms of the Stockholders Agreement.

(c) Irrevocable. Subject to the foregoing Section 12(b), during the term of this Agreement the Trust hereby created shall be irrevocable and no Shares of Horizon held by the Voting Trustee pursuant to the terms of this Agreement shall be transferred to or upon the order of the holder of a Voting Trust Certificate evidencing the beneficial ownership thereof prior to the termination of this Agreement.

13. Delivery of Stock Certificates Upon Termination of this Agreement.

(a) Stock Certificates. Upon termination of this Agreement, the Voting Trustee, in exchange for and upon surrender of any Voting Trust Certificates then outstanding, shall, in accordance with the terms hereof, deliver certificates for capital stock of Horizon of the series or class and in the amount called for by such Voting Trust Certificate and either registered in the name of the holder thereof or duly endorsed in blank or accompanied by proper instruments of assignment and transfer thereof duly executed in blank to the holder thereof, and the Voting Trustee may require the holder of such Voting Trust Certificate to surrender the same for such exchange.

(b) Obligations of Trustee. After any termination of this Agreement as above provided with respect to all Shares, and delivery by the Voting Trustee of any stock or other property then held hereunder in exchange for outstanding Voting Trust Certificates as provided in this Section 13, all further obligations or duties of the Voting Trustee under this Agreement or any provision hereof shall cease.

14. Resignation; Successor Trustee. The Voting Trustee may resign at any time by providing Horizon and each Stockholder with written notice to such effect 30 days prior to the effective date of such resignation. If for any reason ▇▇▇▇ ▇. ▇▇▇▇▇▇ shall cease to serve as Voting Trustee hereunder, his immediate successor in such capacity shall be ▇▇▇▇▇▇▇ ▇. ▇▇▇▇▇▇; provided that (i) the person serving as Voting Trustee may at any time, and from time to time, replace or designate the successor to such Voting Trustee and (ii) each such successor shall be an officer of ▇▇▇▇▇▇ ▇▇▇▇▇▇, Inc. or an officer of ▇▇▇▇▇▇ ▇▇▇▇▇▇ Partners IV GP, Inc. Each such successive designated person shall, upon assuming the duties hereunder upon a vacancy occurring in the office of Voting Trustee, be the Voting Trustee.

15. Interests Allowed as Voting Trustee. The Voting Trustee may be a creditor or stockholder of Horizon and may act as a director, officer or employee of, or consultant or advisor to, Horizon and receive compensation therefor. In addition, the Voting Trustee and any firm of which he may be a member, and any of his affiliates, may contract with Horizon or have a pecuniary interest in any matter or transaction to which Horizon may be a party, or in which Horizon may be in any way concerned.

16. Effect of Agreement Upon Representatives, Successors and Assigns. This Agreement shall inure to the benefit of and be binding upon the Voting Trustee and each Stockholder and their respective legal representatives, successors and assigns.

17. Miscellaneous.

(a) Deliver to Stockholders. The Voting Trustee shall deliver to each Stockholder all information received by the Voting Trustee from Horizon or from other stockholders of Horizon.

(b) Assignment; Binding Effect. Except as otherwise provided in this Agreement, no right under this Agreement shall be assignable and any attempted assignment in violation of this provision shall be void. This Agreement, and the rights and obligations of the parties hereunder, shall be binding upon and inure to the benefit of any and all successors, permitted assigns, personal representatives and all other legal representatives, in whatsoever capacity, by operation of law or otherwise, of the parties hereto, in each case with the same force and effect as if the foregoing persons were named herein as parties hereto.

(c) Notices. All notices to be given to the owners of Voting Trust Certificates shall be given by mailing the same in a sealed postpaid envelope to the registered owners of Voting Trust Certificates addressed to their respective addresses as shown on the books of the Trust, and any notice whatsoever when mailed by or on behalf of the Voting Trustee to such registered owners of Voting Trust Certificates as herein provided shall have the same effect as though personally served on all holders of Voting Trust Certificates. All notices to be given to the Voting Trustee shall be given by serving a copy thereof upon him personally or by mailing the same in a sealed postpaid envelope addressed to him at his address set forth below or to such other address as he shall from time to time in writing designate. All notices to Horizon shall be given by mailing the same in a sealed postpaid envelope addressed to it at its address set forth below or to such other address as it shall from time to time in writing designate.

if to Horizon, to it at:

c/o ▇▇▇▇▇▇ ▇▇▇▇▇▇, Inc.

▇▇▇ ▇▇▇▇ ▇▇^▇▇ ▇▇▇▇▇▇

▇▇^▇▇ ▇▇▇▇▇

▇▇▇ ▇▇▇▇, ▇▇▇ ▇▇▇▇ ▇▇▇▇▇

Attention: ▇▇▇▇▇▇ ▇▇▇▇▇▇▇▇

Telecopier No.: ▇▇▇-▇▇▇-▇▇▇▇

with a copy to:

▇▇▇▇▇▇ ▇▇▇▇▇▇, Inc.

▇▇▇ ▇▇▇▇ ▇▇^▇▇ ▇▇▇▇▇▇

▇▇^▇▇ ▇▇▇▇▇

▇▇▇ ▇▇▇▇, ▇▇▇ ▇▇▇▇ ▇▇▇▇▇

Attention: ▇▇▇▇▇▇ ▇▇▇▇▇

Telecopier No.: ▇▇▇-▇▇▇-▇▇▇▇

and to:

▇▇▇▇▇▇▇ ▇▇▇▇ & ▇▇▇▇▇ LLP

▇▇▇ ▇▇▇▇▇ ▇▇▇▇▇▇

▇▇▇ ▇▇▇▇, ▇▇ ▇▇▇▇▇

Attention: ▇▇▇▇▇ ▇▇▇▇▇, Esq.

Telecopier No.: ▇▇▇-▇▇▇-▇▇▇▇

if to the Voting Trustee, to it at:

c/o ▇▇▇▇▇▇ ▇▇▇▇▇▇, Inc.

▇▇▇ ▇▇▇▇ ▇▇^▇▇ ▇▇▇▇▇▇

▇▇^▇▇ ▇▇▇▇▇

▇▇▇ ▇▇▇▇, ▇▇▇ ▇▇▇▇ ▇▇▇▇▇

Attention: ▇▇▇▇ ▇. ▇▇▇▇▇▇

Telecopier No.: ▇▇▇-▇▇▇-▇▇▇▇

with a copy to:

▇▇▇▇▇▇ ▇▇▇▇▇▇, Inc.

▇▇▇ ▇▇▇▇ ▇▇^▇▇ ▇▇▇▇▇▇

▇▇^▇▇ ▇▇▇▇▇

▇▇▇ ▇▇▇▇, ▇▇▇ ▇▇▇▇ ▇▇▇▇▇

Attention: ▇▇▇▇▇▇ ▇▇▇▇▇

Telecopier No.: ▇▇▇-▇▇▇-▇▇▇▇

and to:

▇▇▇▇▇▇▇ ▇▇▇▇ & ▇▇▇▇▇ LLP

▇▇▇ ▇▇▇▇▇ ▇▇▇▇▇▇

▇▇▇ ▇▇▇▇, ▇▇ ▇▇▇▇▇

Attention: ▇▇▇▇▇ ▇▇▇▇▇, Esq.

Telecopier No.: ▇▇▇-▇▇▇-▇▇▇▇

(d) Filing of Agreement. Until the termination of this Agreement, one original counterpart hereof shall be filed at each of (i) the principal office of Horizon and (ii) the registered office of Horizon in the State of Delaware, and each such counterpart shall be open to the inspection of any holder of any Voting Trust Certificate or any stockholder of Horizon daily during business hours.

(e) Amendment. If at any time it is deemed advisable for the parties hereto to amend or revoke this Agreement, it may be amended or revoked by an agreement executed by the Voting Trustee, Horizon and the holder or holders of all of the Voting Trust Certificates.

(f) Acknowledgment of Obligations. The Voting Trustee accepts the trust created hereby subject to all the terms and conditions herein contained and agrees that he

will exercise the powers and perform the duties of Voting Trustee as set forth herein according to his best judgment.

(g) Applicable Law; Consent to Jurisdiction. This Agreement and the validity and performance of the terms hereof shall be governed by and construed in accordance with the laws of the State of New York without regard to principles of conflicts of law or choice of law. The parties hereto hereby agree that all actions or proceedings arising directly or indirectly from or in connection with this Agreement shall be litigated only in the Supreme Court of the State of New York or the United States District Court for the Southern District of New York located in New York County, New York. To the extent permitted by applicable law, the parties hereto consent to the jurisdiction and venue of the foregoing courts and consent that any process or notice of motion or other application to either of said courts or a judge thereof may be served inside or outside the State of New York or the Southern District of New York by registered mail, return receipt requested, directed to such party at its address set forth in this Agreement (and service so made shall be deemed complete five days after the same has been posted as aforesaid) or by personal service or in such other manner as may be permissible under the rules of said courts.

(h) Entire Agreement; Amendments and Waivers. This Agreement sets forth the entire understanding of the parties with respect to the subject matter hereof. The failure of any party to seek redress for the violation of or to insist upon the strict performance of any term of this Agreement shall not constitute a waiver of such term and such party shall be entitled to enforce such term without regard to such forbearance. This Agreement may be amended only by the written consent of each party hereto, and each party hereto may take any action herein prohibited or omit to take action herein required to be performed by it, and any breach of or compliance with any covenant, agreement, warranty or representation may be waived only by the written waiver of the party against whom such action or inaction may negatively affect, but, in any case, such consent or waiver shall only be effective in the specific instance and for the specific purpose for which given.

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

(j) Severability. If any term, provision, covenant or restriction of this Agreement, or any part thereof, is held by a court of competent jurisdiction or any foreign federal, state, county or local government or any other governmental, regulatory or administrative agency or authority to be invalid, void, unenforceable or against public policy for any reason, the remainder of the terms, provisions, covenants and restrictions of this Agreement shall remain in full force and effect and shall in no way be affected, impaired or invalidated.

(k) Counterparts. This Agreement may be executed in two or more counterparts, each of which shall be deemed an original, but all of which shall constitute one and the same instrument, and it shall not be necessary in making proof of this Agreement to produce or account for more than one such counterpart.

(l) Specific Performance. Each of the parties hereto acknowledges and agrees that in the event of any breach of this Agreement, the non-breaching party would be

irreparably harmed and could not be made whole by monetary damages. It is accordingly agreed that the parties hereto shall and do hereby waive the defense in any action for specific performance that a remedy at law would be adequate and that the parties hereto, in addition to any other remedy to which they may be entitled at law or in equity, shall be entitled to compel specific performance of this Agreement in any action instituted in the Supreme Court of the State of New York or the United States District Court for the Southern District of New York, or, in the event such courts shall not have jurisdiction of such action, in any court of the United States or any state thereof having subject matter jurisdiction of such action.

[Remainder of Page Intentionally Left Blank.]

IN WITNESS WHEREOF, the parties hereto have duly executed this Agreement as of the day and year first above written.


COMPANY:

HORIZON LINES HOLDING CORP.

/s/ ▇▇▇▇▇▇▇ ▇. ▇▇▇▇▇▇▇
Name:		▇▇▇▇▇▇▇ ▇. ▇▇▇▇▇▇▇
Title:		President and Chief Executive Officer

[Signature Page to Horizon Lines Holding Corp. Voting Trust Agreement]

VOTING TRUSTEE:

/s/ ▇▇▇▇ ▇. ▇▇▇▇▇▇

▇▇▇▇ ▇. ▇▇▇▇▇▇

c/o ▇▇▇▇▇▇ ▇▇▇▇▇▇, Inc.

▇▇▇ ▇▇▇▇ ▇▇▇▇ ▇▇▇▇▇▇ ▇▇▇▇ ▇▇▇▇▇

▇▇▇ ▇▇▇▇, ▇▇▇ ▇▇▇▇ ▇▇▇▇▇

[Signature Page to Horizon Lines Holding Corp. Voting Trust Agreement]