Exhibit 5.1

Paul, Weiss, Rifkind, Wharton & Garrison LLP

1285 Avenue of the Americas

New York, NY 10019-6064

October 22, 2024

RXO, Inc.
11215 North Community House Road

Charlotte, NC 28277

Registration Statement on Form S-3ASR
(Registration No. 333-282002)

Ladies and Gentlemen:

We have acted as special counsel to RXO, Inc., a Delaware corporation (the “Company”), in connection with the Registration Statement on Form S-3ASR (File No. 333–282002) (the “Registration Statement”), which became effective on September 9, 2024. You have asked us to furnish our opinion as to the legality of (i) 28,514,952 shares (the “Common Shares”) of common stock of the Company, par value $0.01 per share (the “Common Stock”), consisting of (A) 22,255,481 shares (the “Issued Shares”) of Common Stock outstanding and (B) 6,259,471 shares (the “Warrant Shares”) of Common Stock issuable upon the exercise of pre-funded warrants to purchase Common Stock (the “Warrants”), all of which are registered under the Registration Statement and which are being offered and sold by certain stockholders of the Company.

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:

1.	the Registration Statement;

2.	the base prospectus dated September 9, 2024 (the “Base Prospectus”);

3.	the prospectus supplement dated October 22, 2024 (the “Prospectus Supplement”); and

4.	the form of Pre-Funded Warrant to Purchase Common Stock, included as Exhibit 4.5 to the Registration Statement.

RXO, Inc.

In addition, we have examined (i) such corporate records of the Company that we have considered appropriate, including a copy of the certificate of incorporation, as amended, and bylaws, as amended, of the Company certified by the Company as in effect on the date of this letter, (ii) copies of resolutions of the board of directors of the Company relating to the issuance of the Securities, certified by the Company and (iii) 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 oral and written statements of officers and representatives of the Company as to factual matters and upon certificates of public officials and the officers of the Company.

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 such 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.

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

1. The Issued Shares have been duly authorized by all necessary corporate action on the part of the Company and the Issued Shares are validly issued, fully paid and non-assessable.

2. The Warrant Shares have been duly authorized by all necessary corporate action on the part of the Company and, when issued, delivered and paid for in accordance with the provisions of the Warrants, the Warrant Shares will be validly issued, fully paid and non-assessable.

The opinions expressed above are limited to the Delaware General Corporation Law. Our opinions are rendered only with respect to the laws, and the rules, regulations and orders under those laws, that are currently in effect.

RXO, Inc.

We hereby consent to use of this opinion as an exhibit to the Company’s Current Report on Form 8-K filed by the Company with the Securities and Exchange Commission (the “Commission”) on the date hereof, and to the use of our name under the heading “Legal Matters” in the Base Prospectus included in the Registration Statement and in the Prospectus Supplement. In giving this consent, we do not hereby admit that we come within the category of persons whose consent is required by the Securities Act of 1933, as amended, or the rules and regulations of the Commission thereunder.

		Very truly yours,

		/s/ Paul, Weiss, Rifkind, Wharton & Garrison LLP PAUL, WEISS, RIFKIND, WHARTON & GARRISON LLP