Exhibit 5.1

[Letterhead of]

CRAVATH, SWAINE & MOORE LLP

[New York Office]

September 25, 2020

Atlas Air Worldwide Holdings, Inc.

625,452 Warrants to Purchase Common Stock, Par Value $0.01

Ladies and Gentlemen:

We have acted as counsel for Atlas Air Worldwide Holdings, Inc., a Delaware corporation (the “Company”), in connection with the registration for resale under the Securities Act of 1933 (the “Securities Act”) of 625,452 warrants (the “Warrants”) to purchase shares of the Company’s common stock, par value $0.01 per share (the “Shares”), by the selling securityholder named in the Prospectus Supplement (as defined below).

In that connection, we have examined originals, or copies certified or otherwise identified to our satisfaction, of such documents, corporate records and other instruments as we have deemed necessary or appropriate for the purposes of this opinion, including: (a) the Certificate of Incorporation, as amended, of the Company; (b) the By-laws, as amended, of the Company; (c) the resolutions adopted by the Board of Directors of the Company on May 27, 2020; (d) the Warrant Agreement, dated May 29, 2020, between the Company and the U.S. Department of the Treasury (the “Warrant Agreement”); and (e) the Registration Statement on Form S-3 (Registration No. 333-237771) filed with the Securities and Exchange Commission (the “Commission”) on April 21, 2020 (the “Registration Statement”), with respect to registration under the Securities Act of an unlimited aggregate amount of various securities of the Company, to be issued from time to time by the Company.

In rendering this opinion, we have assumed, with your consent and without independent investigation or verification, the genuineness of all signatures, the legal capacity and competency of all natural persons, the authenticity of all documents submitted to us as originals and the conformity to authentic original documents of all documents submitted to us as duplicates or copies. We have relied, with respect to factual matters, on statements of public officials and officers and other representatives of the Company.

Based on the foregoing and subject to the qualifications set forth herein, we are of the opinion that (i) the Warrants have been validly issued and constitute valid and binding obligations of the Company (subject to applicable bankruptcy, insolvency, reorganization, fraudulent conveyance, moratorium or other similar laws affecting creditors’ rights generally from time to time in effect and subject to general principles of equity, including, without limitation, concepts of materiality, reasonableness, good faith and fair dealing, regardless of whether such enforceability is considered in a proceeding in equity or at law); and (ii) the Shares, when issued and delivered against payment therefor in accordance with the terms of the Warrant Agreement, will be validly issued, fully paid and nonassessable.

2

We are admitted to practice in the State of New York, and we express no opinion as to matters governed by any laws other than the laws of the State of New York and the General Corporation Law of the State of Delaware.

We hereby consent to the filing of this opinion with the Commission as Exhibit 5.1 to the Current Report on Form 8-K dated the date hereof and incorporated by reference into the Registration Statement. We also consent to the reference to our firm under the caption “Validity of Securities” in the Prospectus Supplement, dated September 25, 2020, constituting part of the Registration Statement (the “Prospectus Supplement”). In giving this consent, we do not hereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the Rules and Regulations of the Commission promulgated thereunder.