Exhibit 5.1

Form of Opinion of Debevoise & Plimpton LLP

[Letterhead of Debevoise & Plimpton LLP]

[—], 2014

xpedx Holding Company

6400 Poplar Ave.

Memphis, TN 38197

Registration Statement on Form S-1

of xpedx Holding Company

(Registration No. 333-193950)

Ladies and Gentlemen:

We have acted as special counsel to xpedx Holding Company, a Delaware corporation (the “Company”), in connection with the filing with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Act”), of the Registration Statement on Form S-1 (File No. 333-193950), as amended (the “Registration Statement”), relating to the registration of shares (the “Shares”) of common stock, par value $0.01 per share (the “Common Stock”), of the Company to be distributed to stockholders of International Paper Company (“International Paper”) in accordance with the terms of the Contribution and Distribution Agreement, dated as of January 28, 2014, among International Paper, the Company, UWW Holdings, Inc. and UWW Holdings, LLC (the “Distribution Agreement”).

In rendering the opinion expressed below, we have (a) examined and relied on the originals, or copies certified or otherwise identified to our satisfaction, of such agreements, documents and records of the Company and International Paper and such other instruments and certificates of public officials, officers and representatives of the Company and International Paper and others as we have deemed necessary or appropriate for the purposes of such opinion, (b) examined and relied as to factual matters upon, and have assumed the accuracy of, the statements made in the certificates of public officials, officers and representatives of the Company and International Paper and others delivered to us and (c) made such investigations of law as we have deemed necessary or appropriate as a basis for such opinions.

In rendering the opinions expressed below, we have assumed, with your permission, without independent investigation or inquiry, (i) the authenticity and completeness of all documents submitted to us as originals, (ii) the genuineness of all signatures on all documents that we examined, (iii) the conformity to authentic originals and completeness of documents submitted to us as certified, conformed or reproduction copies, (iv) the legal capacity of all natural persons executing documents, (v) the filing of the Company’s Amended and Restated Certificate of Incorporation, in the form filed as Exhibit 3.3 to the Registration Statement, with the Secretary of State of the State of Delaware and (vi) the consummation of the transactions contemplated by the Distribution Agreement in accordance with the terms thereof.

Based upon and subject to the foregoing and the assumptions, qualifications and limitations hereinafter set forth, we are of the opinion that, when the shares of Common Stock issuable pursuant to the Distribution Agreement have been issued and delivered in accordance with the terms of the Distribution Agreement, the Shares will be validly issued, fully paid and non-assessable.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference to our firm under the caption “Legal Matters” in the Prospectus forming a part thereof. In giving such consent, we do not concede that we are within the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission thereunder.

We are members of the bar of the State of New York. We express no opinion as to the laws of any jurisdiction other than the Delaware General Corporation Law as currently in effect.

Very truly yours,

/s/ Debevoise & Plimpton LLP