Exhibit 5.1

Paul, Weiss, Rifkind, Wharton & Garrison LLP

1285 Avenue of the Americas

New York, NY 10019-6064

212-373-3000

212-757-3990

July 2, 2015

Verso Paper Holdings LLC

Verso Paper Inc.

6775 Lenox Center Court, Suite 400

Memphis, TN 38115-4436

Registration Statement on Form S-4

Ladies and Gentlemen:

In connection with the Registration Statement on Form S-4 (the “Registration Statement”) of Verso Paper Holdings LLC, a Delaware limited liability company (the “Issuer”), Verso Paper Inc., a Delaware corporation (the “Co-Issuer” and, together with the Issuer, the “Issuers”), the persons listed on Schedule I hereto (each, a “Delaware Corporate Guarantor”), the persons listed on Schedule II hereto (each, a “Delaware LLC Guarantor”, and together with the Delaware Corporate Guarantors, the “Delaware Guarantors”) and nexTier Solutions Corporation, a California corporation (the “California Guarantor” and, together with the Delaware Guarantors, the “Guarantors”),

Verso Paper Holdings, LLC and Verso Paper Inc. 2

filed with the Securities and Exchange Commission pursuant to the Securities Act of 1933, as amended (the “Act”), and the rules and regulations thereunder (the “Rules”), you have asked us to furnish our opinion as to the legality of the securities being registered under the Registration Statement. The Registration Statement relates to the registration under the Act of (i) $180,767,777 aggregate principal amount of the Issuers’ Second Priority Adjustable Senior Secured Notes (the “Second Priority Exchange Notes”) and the guarantees of the Second Priority Exchange Notes by the Guarantors (the “Second Priority Note Guarantees”) and (ii) $65,026,237 aggregate principal amount of the Issuers’ Adjustable Senior Subordinated Notes (the “Subordinated Exchange Notes” and, together with the Second Priority Exchange Notes, the “Exchange Notes”) and the guarantees of the Subordinated Exchange Notes by the Guarantors (the “Subordinated Note Guarantees” and, together with the Second Priority Guarantees, the “Guarantees” and, the Guarantees collectively with the Exchange Notes, the “Securities”).

The Securities are to be offered in exchange for the Issuers’ outstanding (i) $180,767,777 aggregate principal amount of unregistered Second Priority Adjustable Senior Secured Notes (the “Original Second Priority Notes”) and the guarantees of the Original Second Priority Notes by the Guarantors and (ii) $65,026,237 aggregate principal amount of unregistered Adjustable Senior Subordinated Notes (the “Original Subordinated Notes” and, together with the Original Second Priority Notes, the “Original Notes”) and the guarantees of the Original Subordinated Notes by the Guarantors. The Second Priority Exchange Notes and the Second Priority Note Guarantees will be issued by the Issuers and the Guarantors in accordance with the terms of the Indenture, dated as of August 1, 2014, as supplemented by the First Supplemental Indenture dated as of January 7, 2015 (as supplemented, the “Second Priority Note Indenture”), among the

Verso Paper Holdings, LLC and Verso Paper Inc. 3

Issuers, the Guarantors and Wilmington Trust, National Association, as trustee. The Subordinated Exchange Notes and the Subordinated Note Guarantees will be issued by the Issuers and the Guarantors in accordance with the terms of the Indenture, dated as of August 1, 2014, as supplemented by the First Supplemental Indenture dated as of January 7, 2015 (as supplemented, the “Subordinated Note Indenture” and, together with the Second Priority Indenture, the “Indentures”), among the Issuers, the Guarantors and Wilmington Trust, National Association, as trustee.

In connection with the furnishing of this opinion, we have examined originals, or copies certified or otherwise identified to our satisfaction, of the following documents (collectively, the “Documents”):

1. the Registration Statement;

2. the Second Priority Note Indenture, including the form of the Second Priority Exchange Notes attached thereto, included as Exhibit 4.5 to the Registration Statement;

3. the Subordinated Note Indenture, including the form of the Subordinated Exchange Notes attached thereto, included as Exhibit 4.7 to the Registration Statement; and

4. the Notes Registration Rights Agreement, dated as of August 1, 2014 (the “Notes Registration Rights Agreement”), by and among Verso Paper Holdings LLC, Verso Paper Inc., the subsidiaries of Verso Paper Holdings LLC party thereto, and Evercore Group L.L.C., Credit Suisse Securities (USA) LLC, and Barclays Capital Inc., as the Dealer Managers, in respect of the Exchange Notes and included as Exhibit 4.8 to the Registration Statement.

Verso Paper Holdings, LLC and Verso Paper Inc. 4

In addition, we have examined (i) such organizational records of the Issuers and the Delaware Guarantors as we have considered appropriate, including, as applicable, a copy of the articles of incorporation, as amended, certificate of formation, as amended, and the limited liability company operating agreement or by-laws, as amended, of the Issuers and the Delaware Guarantors, certified by the Issuers and the Delaware Guarantors as in effect on the date of this letter, and copies of resolutions of the board of directors or other governing body, as applicable, of the Issuers and the Delaware Guarantors relating to the issuance of the Securities, certified by the Issuers and the Delaware Guarantors and (ii) such other certificates, agreements and documents as we deemed relevant and necessary as a basis for the opinions expressed below. We have also relied upon the representations and warranties of the Issuers and the Guarantors made in the Documents as to factual matters and upon certificates of public officials and the officers of the Issuers and the Guarantors.

In our examination of the documents referred to above, we have assumed, without independent investigation, the genuineness of all signatures, the legal capacity of all individuals who have executed any of the documents reviewed by us, the authenticity of all documents submitted to us as originals, the conformity to the originals of all documents submitted to us as certified, photostatic, reproduced or conformed copies of valid existing agreements or other documents, the authenticity of all the latter documents and that the statements regarding matters of fact in the certificates, records, agreements, instruments and documents that we have examined are accurate and complete. We have also assumed, without independent investigation, that (i) the Securities will be issued as described in the Registration Statement, (ii) the Exchange Notes will be in substantially the form attached to the Indentures and that any information omitted from such form will

Verso Paper Holdings, LLC and Verso Paper Inc. 5

be properly added, (iii) the California Guarantor is validly existing and in good standing under the laws of its jurisdiction of organization, and (iv) the California Guarantor has all necessary power and authority to execute, deliver and perform its obligations under Indentures and the Guarantees, as applicable. We have relied, with the Company’s permission, upon the opinion of O’Melveny & Myers LLP, dated as of the date hereof and filed as Exhibit 5.2 to the Registration Statement as to due authorization, execution and delivery of the Indentures and the Guarantees, as applicable, by the California Guarantor.

Based upon the above, and subject to the stated assumptions, exceptions and qualifications, we are of the opinion that:

1. When duly issued, authenticated and delivered against the surrender and cancellation of the Original Notes as set forth in the Registration Statement and in accordance with the terms of the related Indentures and the Notes Registration Rights Agreement, the Exchange Notes will constitute legal, valid and binding obligations of the Issuers, enforceable against the Issuers in accordance with their terms, except that the enforceability of the Exchange Notes may be subject to bankruptcy, insolvency, reorganization, fraudulent conveyance or transfer, moratorium or similar laws affecting creditors’ rights generally and subject to general principles of equity (regardless of whether enforceability is considered in a proceeding in equity or at law).

2. When the Exchange Notes are duly issued, authenticated and delivered against the surrender and cancellation of the Original Notes as set forth in the Registration Statement and in accordance with the terms of the related Indentures and the Notes Registration Rights Agreement, the Guarantees will constitute legal, valid and binding obligations of each of the Guarantors, enforceable against each of the Guarantors

Verso Paper Holdings, LLC and Verso Paper Inc. 6

in accordance with their terms, except that enforceability of the Guarantees may be subject to bankruptcy, insolvency, reorganization, fraudulent conveyance or transfer, moratorium or similar laws affecting creditors’ rights generally and subject to general principles of equity (regardless of whether enforcement is considered in a proceeding in equity or at law).

The opinions expressed above are limited to the laws of the State of New York, the General Corporation Law of the State of Delaware and the Limited Liability Company Act of the State of Delaware. Our opinion is rendered only with respect to the laws, and the rules, regulations and orders under those laws, that are currently in effect.

We hereby consent to use of this opinion as an exhibit to the Registration Statement and to the use of our name under the heading “Legal Matters” contained in the prospectus included in the Registration Statement. In giving this consent, we do not thereby admit that we come within the category of persons whose consent is required by the Act or the Rules.

Very truly yours,

/s/ PAUL, WEISS, RIFKIND, WHARTON & GARRISON LLP

PAUL, WEISS, RIFKIND, WHARTON & GARRISON LLP

SCHEDULE I

DELAWARE CORPORATE GUARANTORS

Name	State of Incorporation / Organization
Verso Quinnesec REP Holding Inc.	Delaware
NewPage Holdings Inc.	Delaware

SCHEDULE II

DELAWARE LLC GUARANTORS

Name	State of Incorporation / Organization
Verso Paper LLC	Delaware
Verso Androscoggin LLC	Delaware
Verso Sartell LLC	Delaware
Verso Quinnesec LLC	Delaware
Verso Maine Energy LLC	Delaware
Verso Fiber Farm LLC	Delaware