UNITED STATES DISTRICT COURT FOR THE DISTRICT OF PUERTO RICO

Exhibit 10.51

UNITED STATES DISTRICT COURT FOR THE

DISTRICT OF PUERTO RICO

PLEA AGREEMENT

(Pursuant to Rule 1l(c)(l)(C) FRCP)

TO THE HONORABLE COURT:

COMES NOW the United States of America through its counsel Christine A. Vamey, Assistant Attorney General of the U.S. Department of Justice, Antitrust Division; Scott D. Hammond, Deputy Assistant Attorney General of the U.S. Department of Justice, Antitrust Division; Brent Snyder, Craig Lee, Michael Whitlock, and Jessica Lefort, Trial Attorneys of the U.S. Department of Justice, Antitrust Division; and defendant Horizon Lines, LLC (“defendant”) through its counsel John M. Nannes, Tiffany Rider, Richard J. Rappaport, and Amy Manning, pursuant to Rule 1l(c)(l)(C) of the Federal Rules of Criminal Procedure, to state to this Honorable Court that they have reached an agreement, the terms and conditions of which are as follows:

RIGHTS OF DEFENDANT

1. The defendant understands its rights:

(a) to be represented by an attorney;

(b) to be charged by Indictment;

1

(c) to plead not guilty to any criminal charge brought against it;

(d) to have a trial by jury, at which it would be presumed not guilty of the charge and the United States would have to prove every essential element of the charged offense beyond a reasonable doubt for it to be found guilty;

(e) to confront and cross-examine witnesses against it and to subpoena witnesses in its defense at trial;

(f) to appeal its conviction if it is found guilty; and

(g) to appeal the imposition of a sentence against it.

AGREEMENT TO PLEAD GUILTY

AND WAIVE CERTAIN RIGHTS

2. The defendant knowingly and voluntarily waives the rights set out in Paragraph l(b)-(f) above. The defendant also knowingly and voluntarily waives the right to file any appeal, any collateral attack, or any other writ or motion, including but not limited to an appeal under 18 U.S.C. § 3742, that challenges the sentence imposed by the Court if that sentence is consistent with or below the recommended sentence in Paragraph 8 of this Plea Agreement, regardless of how the sentence is determined by the Court. This agreement does not affect the rights or obligations of the United States as set forth in 18 U.S.C. § 3742(b)-(c). Nothing in this paragraph, however, shall act as a bar to the defendant perfecting any legal remedies it may otherwise have on appeal or collateral attack respecting claims of ineffective assistance of counsel or prosecutorial misconduct. The defendant agrees that there is currently no known evidence of ineffective assistance of counsel or prosecutorial misconduct. Pursuant to Fed. R. Crim. P. 7(b), the defendant will waive indictment and plead guilty at arraignment to a one-count

2

Information to be filed in the United States District Court for the District of Puerto Rico. The Information will charge the defendant with participating in a combination and conspiracy to suppress and eliminate competition by agreeing to fix rates and surcharges for Puerto Rico freight services, from at least as early as May 2002 until at least April 2008, in violation of the Sherman Antitrust Act, 15 U.S.C. § 1.

3. The defendant, pursuant to the terms of this Plea Agreement and the Plea Agreement Supplement filed separately with the Court under seal, will plead guilty to the criminal charge described in Paragraph 2 above and will make a factual admission of guilt to the Court in accordance with Fed. R. Crim. P. 11, as set forth in Paragraph 4 below.

FACTUAL BASIS FOR OFFENSE CHARGED

4. Had this case gone to trial, the United States would have presented evidence sufficient to prove the following facts against the defendant:

(a) For purposes of this Plea Agreement, the “relevant period” is that period from at least as early as May 2002, until at least April 2008. During the relevant period, the defendant was a limited liability company organized and existing under the laws of the State of Delaware. The defendant has its principal place of business in Charlotte, North Carolina and offices in Guaynabo, Puerto Rico. During the relevant period, the defendant provided water transportation for freight between the continental United States and Puerto Rico (“Puerto Rico freight services”). The defendant’s Puerto Rico freight services transported for customers a variety of cargo shipments, such as heavy equipment, medicines, and consumer goods, on scheduled ocean voyages between the continental United States and Puerto Rico. For its Puerto Rico freight services, the

3

defendant charged its customers a price that consisted of a base rate and, at times, various surcharges and fees, such as a bunker fuel surcharge. During the relevant period, the defendant’s sales of Puerto Rico freight services between the continental United States and Puerto Rico totaled approximately $1.4 billion.

(b) During the relevant period, the defendant, through certain of its officers and employees, including high-level personnel of the defendant, participated in a conspiracy with other providers of Puerto Rico freight services, a primary purpose of which was to suppress and eliminate competition by fixing the rates and surcharges charged to customers for Puerto Rico freight services. In furtherance of the conspiracy, the defendant, through certain of its officers and employees, engaged in discussions and attended meetings with representatives of other providers of Puerto Rico freight services. During these discussions and meetings, agreements were reached to fix the rates and surcharges to be charged to customers for Puerto Rico freight services.

(c) During the relevant period, water freight shipments provided by one or more of the conspirator carriers, and the vessels necessary to transport the water freight shipments, as well as payments for the water freight shipments, traveled in interstate commerce. The business activities of the defendant and its co-conspirators in connection with the sale and provision of Puerto Rico freight services affected by this conspiracy were within the flow of, and substantially affected, interstate commerce.

(d) Acts in furtherance of this conspiracy were carried out within the District of Puerto Rico. The conspiratorial meetings and discussions described above took place in the continental United States and Puerto Rico, and a representative of the defendant

4

participated in such discussions in Puerto Rico. Additionally, the Puerto Rico freight services that were the subject of this conspiracy were sold by one or more of the conspirators to customers in this District

POSSIBLE MAXIMUM SENTENCE

5. The defendant understands that the statutory maximum penalty which may be imposed against it upon conviction for a violation of Section One of the Sherman Antitrust Act is a fine in an amount equal to the greatest of:

(a) $100 million (15 U.S.C. § 1);

(b) twice the gross pecuniary gain the conspirators derived from the crime (18 U.S.C. §3571(c) and (d)); or

(c) twice the gross pecuniary loss caused to the victims of the crime by the conspirators (18 U.S.C. § 3571(c) and (d)).

6. In addition, the defendant understands that:

(a) pursuant to 18 U.S.C. § 3561 (c)(l), the Court may impose a term of probation of at least one year, but not more than five years;

(b) pursuant to §8B1.1 of the United States Sentencing Guidelines (“U.S.S.G.,” “Sentencing Guidelines,” or “Guidelines”) or 18 U.S.C. § 3563(b)(2) or 3663(a)(3), the Court may order it to pay restitution to the victims of the offense; and

(c) pursuant to 18 U.S.C. § 3013(a)(2)(B), the Court is required to order the defendant to pay a $400 special assessment upon conviction for the charged crime.

5

SENTENCING GUIDELINES

7. The defendant understands that the Sentencing Guidelines are advisory, not mandatory, but that the Court must consider the Guidelines in effect on the day of sentencing, along with the other factors set forth in 18 U.S.C. § 3553(a), in determining and imposing sentence. The defendant understands that the Guidelines determinations will be made by the Court by a preponderance of the evidence standard. The defendant understands that although the Court is not ultimately bound to impose a sentence within the applicable Guidelines range, its sentence must be reasonable based upon consideration of all relevant sentencing factors set forth in 18 U.S.C. § 3553(a). Pursuant to U.S.S.G. §1B1.8, the United States agrees that self-incriminating information that the defendant and its directors, officers and employees have provided or may provide to the United States pursuant to this Plea Agreement or the Plea Agreement Supplement will not be used to increase the volume of affected commerce attributable to the defendant or in determining the defendant’s applicable Guidelines range, except to the extent provided in U.S.S.G. §lB1.8(b).

SENTENCING AGREEMENT

8. Pursuant to Fed. R. Crim. P. 1 l(c)(l)(C), the United States and the defendant agree that the appropriate disposition of this case is, and agree to recommend jointly that the Court impose, a sentence requiring the defendant to pay to the United States a criminal fine of $45 million, payable in installments as set forth below without interest pursuant to 18 U.S.C. § 3612(f)(3)(A) (“the recommended sentence”). The parties agree that there exists no aggravating or mitigating circumstance of a kind, or to a degree, not adequately taken into consideration by the U.S. Sentencing Commission in formulating the Sentencing Guidelines justifying a departure

6

pursuant to U.S.S.G. §5K2.0. The parties agree not to seek or support any sentence outside of the Guidelines range nor any Guidelines adjustment for any reason that is not set forth in this Plea Agreement. The parties further agree that the recommended sentence set forth in this Plea Agreement is reasonable.

(a) The United States and the defendant agree that the applicable Guidelines fine range exceeds the fine contained in the recommended sentence set out in Paragraph 8 above but agree that imposition of a fine greater than that recommended would substantially jeopardize the defendant’s continued viability. The parties further agree that the recommended fine is appropriate, pursuant to U.S.S.G. §8C3.3(a) and (b).

(b) The United States and the defendant agree to recommend, in the interest of justice pursuant to 18 U.S.C. § 3572(d)(l) and U.S.S.G. §8C3.2(b), that the fine be paid in the following installments: within thirty (30) days of imposition of sentence — $1 million; at the one-year anniversary of imposition of sentence (“anniversary”) — $1 million; at the two-year anniversary — $3 million; at the three-year anniversary — $5 million; at the four-year anniversary — $15 million; and at the five-year anniversary — $20 million; provided, however, that the defendant shall have the option at any time before the five-year anniversary of prepaying any part of the remaining balance then owing on the fine.

(c) The defendant understands that the Court will order it to pay a $400 special assessment, pursuant to 18 U.S.C. § 3013(a)(2)(B), in addition to any fine imposed.

7

(d) The United States may recommend that the Court order a term of probation. The defendant may recommend that no term of probation be imposed. The parties understand that the Court’s decision regarding the imposition of probation will not void this Plea Agreement or the Plea Agreement Supplement.

(e) If the United States does not recommend a term of probation, the United States and the defendant jointly submit that this Plea Agreement, together with the record that will be created by the United States and the defendant at the plea and sentencing hearings, and the further disclosure described in the Plea Agreement Supplement that is being filed under seal, will provide sufficient information concerning the defendant, the crime charged in this case, and the defendant’s role in the crime to enable the meaningful exercise of sentencing authority by the Court under 18 U.S.C. § 3553. The United States and defendant agree to request jointly that the Court accept the defendant’s guilty plea and impose sentence on an expedited schedule as early as the date of arraignment if the United States does not recommend a term of probation, based upon the record provided by the defendant and the United States, under the provisions of Fed. R. Crim. P. 32(c)(l)(A)(ii) and U.S.S.G. §6A1.1. The Court’s denial of the request to impose sentence on an expedited schedule will not void this Plea Agreement or the Plea Agreement Supplement.

9. The United States and the defendant understand that the Court retains complete discretion to accept or reject the recommended sentence provided for in Paragraph 8 of this Plea Agreement.

8

(a) If the Court does not accept the recommended sentence, the United States and the defendant agree that this Plea Agreement, except for Paragraph 9(b) below, and the Plea Agreement Supplement shall be rendered void.

(b) If the Court does not accept the recommended sentence, the defendant will be free to withdraw its guilty plea (Fed. R. Crim. P. 1l(c)(5) and (d)). If the defendant withdraws its plea of guilty, this Plea Agreement, the Plea Agreement Supplement, the guilty plea, and any statement made in the course of any proceedings under Fed. R. Crim. P. 11 regarding the guilty plea, this Plea Agreement, or the Plea Agreement Supplement, or made in the course of plea discussions with an attorney for the government shall not be admissible against the defendant in any criminal or civil proceeding, except as otherwise provided in Fed. R. Evid. 410. In addition, the defendant agrees that, if it withdraws its guilty plea pursuant to this subparagraph of the Plea Agreement, the statute of limitations period for any offense referred to in Paragraph 11 of this Plea Agreement shall be tolled for the period between the date of the signing of the Plea Agreement and the date the defendant withdrew its guilty plea or for a period of sixty (60) days after the date of the signing of the Plea Agreement, whichever period is greater.

10. In light of pending civil class action lawsuits filed against the defendant, which potentially provide for a recovery of a multiple of actual damages, the United States agrees that it will not seek a restitution order for the offense charged in the Information.

9

GOVERNMENT’S AGREEMENT

11. Upon acceptance of the guilty plea called for by this Plea Agreement and the imposition of the recommended sentence, and subject to the requirements of the Plea Agreement Supplement, the United States agrees that it will not bring further criminal charges against the defendant or any of its subsidiaries; Horizon Lines, Inc.; Horizon Lines Holding Corporation; o Horizon Lines of Puerto Rico, Inc. (collectively “related entities”) for any act or offense committed before the date of this Plea Agreement that was undertaken in furtherance of an antitrust conspiracy involving the sale of Puerto Rico freight services. The nonprosecution terms of this paragraph do not apply to civil matters of any kind, to any violation of the federal tax or securities laws, or to any crime of violence.

12. The defendant understands that it may be subject to administrative action by federal or state agencies other than the United States Department of Justice, Antitrust Division, based upon the conviction resulting from the Plea Agreement, and that this Plea Agreement and the Plea Agreement Supplement in no way control whatever action, if any, other agencies may take. However, the United States agrees that, if requested, it will advise the appropriate officials of any governmental entity considering such administrative action of the fact, manner, and extent of the cooperation of the defendant as a matter for that agency to consider before determining what administrative action, if any, to take.

REPRESENTATION BY COUNSEL

13. The defendant has been represented by counsel and is fully satisfied that its attorneys have provided competent legal representation. The defendant has thoroughly reviewed this Plea Agreement, the Plea Agreement Supplement, and Exhibits A - C to the Plea Agreement Supplement and acknowledges that counsel has advised it of the nature of the charge, any possible defenses to the charge, and the nature and range of possible sentences.

10

VOLUNTARY PLEA

14. The defendant’s decision to enter into this Plea Agreement and the Plea Agreement Supplement and to tender a plea of guilty is freely and voluntarily made and is not the result of force, threats, assurances, promises, or representations other than the representations contained in this Plea Agreement, the Plea Agreement Supplement, and Exhibits A - C of the Plea Agreement Supplement. The United States has made no promises or representations to the defendant as to whether the Court will accept or reject the recommendations contained within this Plea Agreement.

VIOLATION OF PLEA AGREEMENT

15. The defendant agrees that, should the United States determine in good faith, during the period that the current federal investigation of violations of federal antitrust and related criminal laws involving the sale of Puerto Rico freight services and any litigation or other proceedings arising or resulting from any such investigation to which the United States is a party is pending, that the defendant or any of its related entities have violated any provision of this Plea Agreement or the Plea Agreement Supplement, the United States will notify counsel for the defendant in writing by personal or overnight delivery or facsimile transmission and may also notify counsel by telephone of its intention to void any of its obligations under this Plea Agreement (except its obligations under this paragraph) or the Plea Agreement Supplement, and the defendant and its related entities shall be subject to prosecution for any federal crime of which the United States has knowledge including, but not limited to, the substantive offenses

11

relating to the investigation resulting in this Plea Agreement and the Plea Agreement Supplement. The defendant and its related entities agree that, in the event that the United States is released from its obligations under this Plea Agreement and the Plea Agreement Supplement and brings criminal charges against the defendant or its related entities for any offense referred to in Paragraph 11 of this Plea Agreement, the statute of limitations period for such offense shall be tolled for the period between the date of the signing of this Plea Agreement and six (6) months after the date the United States gave notice of its intent to void its obligations under this Plea Agreement or the Plea Agreement Supplement.

16. The defendant understands and agrees that in any further prosecution of it or its related entities resulting from the release of the United States from its obligations under this Plea Agreement or the Plea Agreement Supplement, because of the defendant’s or its related entities’ violation of the Plea Agreement or Plea Agreement Supplement, any documents, statements, information, testimony, or evidence provided by it, its related entities, or current directors, officers, or employees of it or its related entities to attorneys or agents of the United States, federal grand juries, or courts, and any leads derived therefrom, may be used against it or its related entities in any such further prosecution. In addition, the defendant unconditionally waives its right to challenge the use of such evidence in any such further prosecution, notwithstanding the protections of Fed. R. Evid. 410.

ENTIRETY OF AGREEMENT

17. This Plea Agreement, the Plea Agreement Supplement filed separately with the Court, and Exhibits A - C of the Plea Agreement Supplement constitute the entire agreement between the United States and the defendant concerning the disposition of the criminal charge in this case. This Plea Agreement and the Plea Agreement Supplement cannot be modified except in writing, signed by the United States and the defendant.

12

18. The undersigned is authorized to enter this Plea Agreement and the Plea Agreement Supplement on behalf of the defendant as evidenced by the Resolution of the Board of Directors of the defendant attached to, and incorporated by reference in, this Plea Agreement.

19. The undersigned attorneys for the United States have been authorized by the Attorney General of the United States to enter this Plea Agreement and the Plea Agreement Supplement on behalf of the United States.

20. A facsimile signature shall be deemed an original signature for the purpose of executing this Plea Agreement and the Plea Agreement Supplement. Multiple signature pages

13

are authorized for the purpose of executing this Plea Agreement and the Plea Agreement Supplement.

14