Exhibit 5.1

Tel + 1.512.542.8400 Fax + 1.512.542.8612

August 1, 2023

New Atlas HoldCo Inc.

5918 W. Courtyard Drive, Suite 500

Austin, Texas 78730

Ladies and Gentlemen:

We are acting as counsel to New Atlas HoldCo Inc., a Delaware corporation (the “Company”), in connection with the preparation and filing with the Securities and Exchange Commission (the “Commission”) of the Registration Statement on Form S-4 to which this letter is attached as an exhibit (as amended or supplemented, the “Registration Statement”), under the Securities Act of 1933, as amended (the “Securities Act”), relating to the proposed issuance by the Company of up to 100,000,000 shares of the Company’s common stock, par value $0.01 per share (“Common Stock,” and such shares to be issued, the “Reorganization Shares”), registered under the Registration Statement, issuable to current stockholders of Atlas Energy Solutions Inc., a Delaware corporation (“Atlas”), upon the consummation of the transactions contemplated by the Master Reorganization Agreement, dated July 31, 2023, by and among Atlas, the Company, AESI Merger Sub Inc., a Delaware corporation, Atlas Sand Operating, LLC, a Delaware limited liability company (“Opco”), Atlas Operating Merger Sub, LLC, a Delaware limited liability company, and Atlas Sand Holdings, LLC, a Delaware limited liability company (the “Master Reorganization Agreement”).

We are rendering the opinion hereinafter set forth as of the time the Registration Statement becomes effective in accordance with Section 8(a) of the Securities Act.

In rendering the opinion hereinafter set forth, we have examined originals or copies, certified or otherwise identified to our satisfaction, of:

(i) the Company’s Certificate of Incorporation;

(ii) the Company’s Bylaws;

(iii) the resolutions dated as of July 31, 2023, adopted by the Special Committee of the board of directors of the Company;

(iv) the resolutions dated as of July 31, 2023, adopted by the board of directors of the Company;

(v) the Master Reorganization Agreement;

(vi) the Registration Statement; and

(vii) such other certificates, statutes and other instruments and documents as we considered appropriate for purposes of the opinion hereafter expressed. As to any facts material to the opinion contained herein, we have made no independent investigation of such facts and have relied, to the extent that we deem such reliance proper, upon certificates of public officials and officers or other representatives of the Company.

Vinson & Elkins LLP Attorneys at Law Austin Dallas Dubai Houston London Los Angeles New York Richmond Riyadh San Francisco Tokyo Washington 200 W. 6^th Street Austin, TX 78701 Tel +1.713.758.2222 Fax +1.713.758.2346 velaw.com

August 1, 2023

In connection with rendering the opinion set forth below, we have assumed that (i) all information contained in all documents we reviewed is true, correct and complete, (ii) all signatures on all documents we reviewed are genuine, (iii) all documents submitted to us as originals are true and complete, (iv) all documents submitted to us as copies are true and complete copies of the originals thereof and (v) all persons executing and delivering the documents we examined have the legal capacity and authority to execute and deliver such documents. In addition, we have assumed that (a) the Registration Statement will have become effective and (b) the Reorganization Shares will be issued in compliance with applicable federal and state securities laws and in the manner described in the Registration Statement and the information statement/prospectus included therein.

Based upon the foregoing, we are of the opinion that the Reorganization Shares, upon issuance and delivery in exchange for (i) the issued and outstanding shares of Class A common stock, par value $0.01 per share, of Atlas, and (ii) the issued and outstanding common membership units in Opco, in accordance with the terms of the Master Reorganization Agreement and in the manner contemplated by the Registration Statement, will be validly issued, fully paid and nonassessable.

This opinion is limited in all respects to the General Corporation Law of the State of Delaware and the federal laws of the United States of America, and we do not express any opinion as to the laws of any other state or jurisdiction.

We hereby consent to the filing by you of this opinion as an exhibit to the Registration Statement, and we further consent to the use of our name under the caption “Legal Matters” in the related information statement/prospectus that forms a part of the Registration Statement. In giving these consents, we do not hereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act.

We express no opinion as to any matter other than as expressly set forth above, and no opinion on any other matter may be inferred or implied herefrom. We undertake no, and hereby expressly disclaim any, obligation to advise the Company or anyone else of any change in any matter set forth herein.

Sincerely,

/s/ Vinson & Elkins L.L.P.