Amended and Restated Put/Call Agreement

AMENDED AND RESTATED PUT/CALL AGREEMENT dated as of September 20, 2005 (this “Agreement”), among HORIZON LINES, INC., a Delaware corporation formerly known as H-Lines Holding Corp. (“Horizon”), and each of the optionholders signatory hereto (each, an “Optionholder”).

On July 7, 2004, Horizon and the Optionholders entered into a certain Put/Call Agreement dated as of July 7, 2004 (the “Original Put/Call Agreement”).

On September 16, 2005, the Board of Directors of Horizon resolved that the stockholders of Horizon consider the adoption and approval of a certain Certificate of Amendment of the Certificate of Incorporation of Horizon (the “Charter Amendment”), pursuant to which each previously authorized share of Common Stock, par value $.01 per share (“Horizon Common Stock”), of Horizon that is issued and outstanding, immediately before the filing of the Charter Amendment with the Secretary of State of the State of Delaware (the “Delaware Secretary”), be automatically, upon the filing of the Charter Amendment with the Delaware Secretary, and, without any act on the part of Horizon, the holder of such share or any other person or entity, changed into and reclassified (the “Reclassification”) into 22.7085016309 shares (such number of Shares, the “Reclassification Multiple”) of Common Stock.

Horizon and the Optionholders now desire to amend and restate the Original Put/Call Agreement to take into account the Reclassification, effective upon the satisfaction of all of the following conditions precedent (collectively, the “Conditions Precedent”): (i) the approval and adoption by the stockholders of the Corporation of the Charter Amendment in accordance the General Corporation Law of the State of Delaware (the “Requisite Stockholder Approval”), (ii) the filing of the Charter Amendment with the Delaware Secretary (the “Charter Amendment Filing”), and (iii) the execution and delivery of this Agreement by Horizon and all of the Optionholders.

1. Effectiveness. This Agreement shall become effective on the date (the “Effective Date”) on which all of the Conditions Precedent have been first satisfied; provided, however, that this Agreement shall not become effective, and the effectiveness of the Original Agreement shall be unaffected by this Agreement, if any of the Conditions Precedent remain unsatisfied as of the 30-day anniversary of the date of this Agreement.

2. Certain Definitions. Capitalized terms used and not otherwise defined in this Agreement shall have the meanings ascribed to them in the Amended and Restated Agreement and Plan of Merger dated July 7, 2004, among Horizon, H-Lines Subcorp., a Delaware corporation (“HLHC”), and TC Group, L.L.C., a Delaware limited liability company, as amended, supplemented or otherwise modified from time to time.

3. Outstanding HLHC Options. Horizon and each Optionholder hereby agree that, as of the date hereof, such Optionholder (i) holds options (the “HLHC Options”) granted by

HLHC prior to July 7, 2005 that are exercisable, assuming that such options are exercised in their entirety solely in exchange for a payment of cash, in the aggregate for the total number of shares of the Common Stock, par value $.01 per share, of HLHC (“HLHC Common Stock”) set forth in the second column on Annex I hereto opposite the name of such Optionholder on Annex I and (ii) such Optionholder does not hold any other shares of capital stock or securities issued by HLHC.

(a) Put Right. Each Optionholder hereby has the right and option (but not the obligation) to require Horizon to assign and transfer, at any time and from time to time, all or any portion of the shares of HLHC Common Stock issued by HLHC on or after the date hereof upon the exercise of the HLHC Options (such shares issued upon such exercise, the “HLHC Shares”) held by such Optionholder in exchange for the issuance by Horizon to such Optionholder of shares of Series A Redeemable Preferred Stock, par value $0.01 per share, of Horizon (the “Horizon Series A Preferred Stock”) and shares of Horizon Common Stock (such shares of Horizon Series A Preferred Stock and Horizon Common Stock so issued, collectively, the “Horizon Shares”) in the quantities determined in accordance with Section 4(e) (such right and option of Optionholder, the “Put Right”).

(b) Call Right. Horizon shall have the right and option (but not the obligation) to require each Optionholder to assign and transfer, at any time and from time to time, to Horizon all or any portion of the HLHC Shares held by such Optionholder in exchange for the issuance and delivery by Horizon to such Optionholder of Horizon Shares in the quantities determined in accordance with Section 4(e) (such right and option of Horizon, the “Call Right”).

(c) Dividend Payments. Upon the exercise of the Put Right or Call Right with respect to any HLHC Shares of an Optionholder, in addition to the Horizon Shares to be received by such Optionholder in exchange for the HLHC Shares to be delivered in respect thereof pursuant to Section 4(a) or 4(b), such Optionholder shall receive from Horizon any dividends or distributions with respect to such Horizon Shares that would have been received by such Optionholder if such Optionholder had exercised the Put Right or Call Right with respect to all of such HLHC Shares on the date hereof and held of record all of the Horizon Shares issued upon the exercise of such Put Right or Call Right from the date hereof up to the date of the exercise of such Put Right or Call Right (the “Past Dividend Payments”).

(i) An Optionholder may exercise its Put Right by providing a written notice to Horizon that states (x) that such Optionholder thereby exercises its Put Right as of the effective date specified in such notice, and (y) the number of HLHC Shares that are to be exchanged upon such exercise; provided, that (a) such effective date shall be a Business Day (or, if not a Business Day, the Business Day thereafter), and (b) in the absence of the inclusion of a valid effective date in such notice, such effective date shall be the date of receipt by Horizon of such written notice.

(ii) Horizon may exercise its Call Right with respect to any Optionholder by providing a written notice to such Optionholder that states (x) that Horizon thereby exercises its Put Right as of the effective date specified in such notice, and (y) the number of HLHC Shares that are to be exchanged upon such exercise; provided, that (a) such effective date shall be a Business Day (or, if not a Business Day, the Business Day thereafter), and (b) in the absence of the inclusion of a valid effective date in such notice, such effective date shall be the date of receipt by Horizon of such written notice.

(e) Calculation of Horizon Shares Issuable. Upon an exercise of either a Put Right or Call Right, the Horizon Shares which shall be issued by Horizon to the applicable Optionholder in exchange for the HLHC Shares specified to be assigned and transferred by such Optionholder to Horizon in such exercise shall consist of (i) that number of shares of Horizon Common Stock (rounded to the nearest whole share) equal to (x) the number of such HLHC Shares multiplied by $497.03 (being the Cash Per Fully-Diluted Common Share), divided by (y) $158, multiplied by (z) the Reclassification Multiplier and (ii) that number of shares of Horizon Series A Preferred Stock (rounded to the nearest whole share) equal to (x) the number of such HLHC Shares multiplied by $497.03, divided by (y) $158, multiplied by (z) 15.

(f) Reservation of Shares and Agreement to be Bound. Horizon shall at all times keep reserved such number of shares of Horizon Common Stock and Horizon Series A Preferred Stock into which all the HLHC Shares held by the Optionholders at such time could be exchanged assuming all the Roll-Over Options were exercised in their entirety, solely in exchange for a payment of cash, and all of the Put Rights or Call Rights were then exercised in their entirety.

(i) The closing of each exchange of HLHC Shares for Horizon Shares pursuant to an exercise of either a Put Right or Call Right in accordance with this Section (each, a “Closing”) shall take place at the offices of Schulte Roth & Zabel LLP, 919 Third Avenue, New York, New York 10022, on the exercise date (the “Closing Date”) for such exercise of such Put Right or Call Right, as determined in accordance with Section 4(d) above.

(ii) At each Closing with respect to any exchange of HLHC Shares for Horizon Shares pursuant to an exercise of either a Put Right or Call Right, (A) Horizon shall (1) issue and deliver to the voting trustee under the Horizon Voting Trust Agreement (as defined below) certificates representing the Horizon Shares to be issued by Horizon to such Optionholder pursuant to this Agreement and (2) deliver to such Optionholder cash in an amount equal to the sum of the Past Dividend Payment Dividends with respect to such Horizon Shares (without any accompanying interest thereon), (B) the applicable Optionholder (or the voting trustee under the HLHC Voting Trust Agreement (as defined below)) shall deliver to Horizon the certificates representing the HLHC Shares to be exchanged therefor, duly endorsed for transfer or accompanied by duly executed stock powers, (C) the applicable Optionholder shall deliver to Horizon such other documents, instruments and writings as may be required to be delivered by such Optionholder in accordance with this Agreement or as may be reasonably requested by Horizon, and (D) Horizon shall deliver to the applicable Optionholder such other documents, instruments and writings as may be required to be delivered by Horizon in accordance with this Agreement or as may be reasonably requested by such Optionholder.

(a) Each Optionholder, on behalf of itself only, makes the following representations and warranties:

(i) Such Optionholder has and is, and will be, acquiring HLHC Shares and Horizon Shares for investment for its own account and not with a view to, or for resale in connection with, the distribution or other disposition thereof in violation of the Securities Act of 1933, as amended (the “Securities Act”). Such Optionholder agrees that it will not, directly or indirectly, offer, transfer, sell, pledge, hypothecate or otherwise dispose of any HLHC Shares or Horizon Shares (or solicit any offers to buy, purchase, or otherwise acquire or take a pledge of any HLHC Shares or Horizon Shares), except in compliance with the Securities Act, the rules and regulations promulgated thereunder, applicable state securities laws, the provisions of this Agreement, the Stockholders Agreement dated as of July 7, 2004, among Horizon, the Optionholders and the other parties thereto, as amended by the First Amendment to Stockholders Agreement dated as of October 15, 2004, and as further amended, supplemented or otherwise modified from time to time (the “Stockholders Agreement”), the Voting Trust Agreement dated as of July 7, 2004, between HLHC and the Optionholders, as amended, supplemented or otherwise modified from time to time (the “HLHC Voting Trust Agreement”), and the Amended and Restated Voting Trust Agreement dated as of October 15, 2005, among Horizon, the Optionholders and the other parties thereto, as amended, supplemented or otherwise modified from time to time (the “Horizon Voting Trust Agreement”). No other person or entity will have any interest, beneficial or otherwise, in the HLHC Shares or Horizon Shares acquired by such Optionholder except as provided under the Stockholders Agreement, the HLHC Voting Trust Agreement, and the Horizon Voting Trust Agreement (collectively, the “Existing Agreements”).

(ii) Such Optionholder acknowledges that it has been advised that (a) neither the HLHC Shares nor the Horizon Shares are registered under the Securities Act, and neither HLHC nor Horizon has any obligation to effectuate any such registration (except, in the case of the Horizon Shares, pursuant to the Stockholders Agreement in accordance with the terms and conditions therein), (b) the HLHC Shares and Horizon Shares must be held indefinitely and such Optionholder must continue to bear the economic risk of its investment in the HLHC Shares and Horizon Shares unless they are subsequently registered under the Securities Act or an exemption from such registration is available, (c) Rule 144 promulgated under the Securities Act is not presently available with respect to the sale of any securities of HLHC or Horizon, and neither HLHC nor Horizon has any obligation nor any intention to make such Rule available, (d) when and if any HLHC Shares or Horizon Shares may be disposed of without registration in reliance on Rule 144, the amounts that may be disposed of may be limited in accordance with the terms and conditions of such Rule, (e) if the Rule 144 exemption is not available, public sale without registration of the HLHC Shares or Horizon Shares will require compliance with Regulation D or some other exemption under the Securities Act, (f) restrictive legends will be placed on the certificates representing the HLHC Shares and Horizon Shares, and (g) a notation will be made in the appropriate records of HLHC and Horizon indicating that the HLHC Shares and Horizon Shares are subject to restrictions on transfer and, if either HLHC or

Horizon should at some time in the future engage the services of a stock transfer agent, appropriate stop-transfer restrictions will be issued to such transfer agent with respect to the HLHC Shares and Horizon Shares.

(iii) Such Optionholder (a) can afford to hold HLHC Shares and Horizon Shares for an indefinite period and to suffer the complete loss of its investment in HLHC Shares and Horizon Shares, and (b) understands and has taken cognizance of all the risk factors related to its acquisition of HLHC Shares and Horizon Shares.

(iv) Such Optionholder’s knowledge and experience in financial and business matters is such that it is capable of evaluating the merits and risks of acquiring HLHC Shares and Horizon Shares.

(v) Such Optionholder will, subject to the provisions of the HLHC Voting Trust Agreement, be entitled to become the record owner and beneficial owner of the HLHC Shares issued upon the exercise of such Optionholder’s HLHC Options, and, subject to the provisions of the HLHC Voting Trust Agreement, such Optionholder will hold such HLHC Shares, and upon the exercise of a Put Right or Call Right with respect to any HLHC Shares of such Optionholder, such Optionholder shall assign and transfer such HLHC Shares to Horizon free and clear of all security interests, liens, claims, pledges, options, rights of first refusal, contracts, limitations on such Optionholder’s voting rights, charges and other encumbrances of any nature whatsoever, except for the Call Right as contemplated by this Agreement and as contemplated by the certificate of incorporation of Horizon, as in effect from time to time, or the Existing Agreements.

(b) Each Optionholder, on behalf of itself only, (i) hereby acknowledges that such Optionholder is a party to the Existing Agreements, that the HLHC Shares issued upon the exercise of such Optionholder’s HLHC Options will be subject to the provisions of the HLHC Voting Trust Agreement (including, without limitation, the voting trust established thereunder), and that the Horizon Shares issued to such Optionholder pursuant to this Agreement shall be subject to the provisions of the Horizon Voting Trust Agreement (including, without limitation, the voting trust continued thereunder) and of the Stockholders Agreement, (ii) hereby acknowledges that, if Horizon or HLHC desires to register any HLHC Shares or Horizon Shares pursuant to a Registration Statement on Form S-8, any Horizon Shares or HLHC Shares acquired by such Optionholder may become subject to a “stock purchase plan” in order to facilitate such registration, provided that the terms of such stock purchase plan are consistent with the provisions of this Agreement and (iii) hereby agrees, if requested by Horizon or HLHC, to approve the terms of such stock purchase plan as it may be established at such time.

(c) Each Optionholder, on behalf of itself only, hereby covenants that if any HLHC Shares or Horizon Shares are disposed of by such Optionholder (i) in reliance upon Rule 144 under the Securities Act, such Optionholder shall deliver to HLHC or Horizon, as applicable, at or prior to the time of such disposition an executed copy of Form 144 (if required by Rule 144) and such other documentation as either HLHC or Horizon, as applicable, may reasonably require in connection with such disposition or (ii) in reliance on Rule 144 or pursuant to another exemption from registration under the Securities Act, such Optionholder shall deliver to HLHC or Horizon, as applicable, a legal opinion, reasonably satisfactory to HLHC or Horizon, as to the availability of and compliance with such exemption.

6. Representations and Warranties of Horizon. Horizon hereby represents and warrants to each Optionholder that the Horizon Shares issuable by Horizon (if any) to such Optionholder pursuant to this Agreement (i) have been reserved for such issuance, (ii) upon the occurrence of the Effective Date, shall be duly authorized, and (iii) upon the issuance and delivery thereof pursuant to this Agreement shall be validly issued and fully paid and non-assessable.

7. Further Action. Each party hereto agrees to execute and deliver any instrument and take any action that may reasonably be requested by any other party for the purpose of effectuating the provisions of this Agreement.

(a) Each party to this Agreement acknowledges and agrees that each certificate issued by HLHC that represents HLHC Shares shall (unless otherwise permitted by the provisions of this Section 8(a)) be stamped or otherwise imprinted with a legend in substantially the following form (in addition to any other legends and other restrictions as Horizon or HLHC may deem necessary or advisable, including, without limitation, restrictions under the certificate of incorporation of HLHC, as in effect from time to time, or any applicable maritime laws or agreements):

“ THE SECURITIES REPRESENTED BY THIS CERTIFICATE HAVE NOT BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933, AS AMENDED (THE “SECURITIES ACT”), AND MAY NOT BE SOLD, TRANSFERRED OR ASSIGNED EXCEPT PURSUANT TO AN EFFECTIVE REGISTRATION STATEMENT UNDER THE SECURITIES ACT OR IN A TRANSACTION EXEMPT FROM REGISTRATION UNDER THE SECURITIES ACT, IN EACH CASE IN ACCORDANCE WITH ANY APPLICABLE SECURITIES LAWS OF ANY STATE. THE SECURITIES REPRESENTED BY THIS CERTIFICATE ARE SUBJECT TO AN AMENDED AND RESTATED PUT/CALL AGREEMENT, DATED AS OF SEPTEMBER 20, 2005, WHICH CONTAINS PROVISIONS REGARDING RESTRICTIONS ON THE TRANSFER OF SUCH SECURITIES AND OTHER MATTERS. A COPY OF SUCH AGREEMENT IS AVAILABLE FOR INSPECTION AT THE PRINCIPAL OFFICE OF HORIZON LINES HOLDING CORP. “

Horizon agrees to cause HLHC to remove the legend set forth above (or a legend in substantially the form thereof) from a certificate representing HLHC Shares (i) upon the assignment and transfer of such HLHC Shares to Horizon pursuant to this Agreement or (ii) otherwise upon Horizon’s determination, in its sole discretion, to do so.

(b) Each party to this Agreement acknowledges and agrees that each certificate issued that represents Horizon Shares issued and delivered by Horizon pursuant to this Agreement shall (unless otherwise permitted by the provisions of this Section 8(b)) be stamped or otherwise imprinted with a legend in substantially the following form (in addition to any other legends and other restrictions as Horizon may deem necessary or advisable, including, without limitation, restrictions under the certificate of incorporation of Horizon, as in effect from time to time, or any applicable maritime laws or agreements):

Horizon agrees to remove the legend set forth above (or a legend in substantially the form thereof) from a certificate representing Horizon Shares if either (i) such Horizon Shares are sold pursuant to an effective registration statement under the Securities Act, (ii) there is delivered to Horizon an opinion of counsel experienced in such matters, in form and substance reasonably satisfactory to Horizon, that such Horizon Shares need no longer be subject to restrictions on resale under the Securities Act, or (iii) otherwise upon Horizon’s determination, in its sole discretion, to do so.

(a) Assignability; Binding Effect. Except as otherwise provided in this Section, no right under this Agreement shall be assignable and any attempted assignment in violation of this provision shall be void. No Optionholder shall sell, transfer, pledge, assign, hypothecate or otherwise dispose of any HLHC Options or HLHC Shares to any Person (other than Horizon), in each case if such Person is not already a party to this Agreement as an Optionholder hereunder, unless and until such Person executes and delivers to Horizon a joinder agreement, in form and substance reasonably acceptable to Horizon, pursuant to which such Person will thereupon become a party to, and be bound by and obligated to comply with the terms and provisions of, (i) this Agreement, as an Optionholder hereunder, (ii) the HLHC Voting Trust Agreement, in the event HLHC Options are so sold, transferred, pledged, assigned, hypothecated or otherwise transferred, (iii) the Stockholders Agreement, as a “Stockholder” thereunder, and (iv) the Horizon Voting Trust Agreement, as a “Stockholder” thereunder. Horizon shall have the right to assign its rights and obligations hereunder to any successor entity (including, without limitation, any entity acquiring substantially all of the assets of Horizon),

whereupon references herein to Horizon shall be deemed to be to such successor. 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.

(b) Notices. Any notice or other communication required or which may be given hereunder shall be in writing and shall be delivered personally, telecopied with confirmed receipt, sent by certified, registered, or express mail, postage prepaid, or sent by a national next-day delivery service to the parties at the following addresses or at such other addresses as shall be specified by the parties by like notice, and shall be deemed given when so delivered personally or telecopied, or if mailed, two business days after the date of mailing, or, if by national next-day delivery service, on the day after delivery to such service as follows:

(c) Applicable Law; Consent. 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.

(d) Entire Agreement; Amendments and Waivers. This Agreement sets forth the entire understanding of the parties with respect to the subject matter hereof and supersedes any and all other agreements with respect to the subject matter hereof, including, but not limited to, the Original Agreement. 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 Horizon and those Optionholders that hold in the aggregate at least 55% of the total number of HLHC Shares issuable upon the exercise of the HLHC Options in their entirety, assuming that such options were exercised solely in exchange for a payment of cash, provided that any such amendment that would materially and disproportionately adversely affect the rights of any particular Optionholder (the “Affected Optionholder”), in its capacity as an Optionholder, in relation to the other Optionholders, in their capacities as Optionholders, shall not be effective as to such Affected Optionholder without such Affected Optionholder’s written consent, 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 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.

(e) Headings; Gender. The headings in this Agreement are for reference purposes only and shall not in any way affect the meaning or interpretations of the Agreement. The use herein of the masculine, feminine or neuter forms shall also denote the other forms, as in each case the context may require.

(f) 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.

(g) 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.

(h) 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.

(i) Survival of Covenants. All covenants, agreements, representations and warranties made herein or in any other document referred to herein or delivered to a party pursuant hereto or in connection herewith shall survive the execution and delivery to such party of this Agreement and of the Horizon Shares.

IN WITNESS WHEREOF, the undersigned have executed this Agreement as of the date first set forth above.


HORIZON LINES, INC.

By:		/s/ ROBERT S. ZUCKERMAN
Name:		Robert S. Zuckerman
Title:		General Counsel and Secretary