Exhibit 5.1

May 23, 2017

Atlas Air Worldwide Holdings, Inc.

$289,000,000 1.875% Convertible Senior Notes due 2024

Ladies and Gentlemen:

We have acted as counsel for Atlas Air Worldwide Holdings, Inc., a Delaware corporation (the “Company”), in connection with the public offering and sale by the Company of $289,000,000 aggregate principal amount of the Company’s 1.875% Convertible Senior Notes due 2024 (the “Securities”) to be issued pursuant to an indenture dated as of June 3, 2015, between the Company and Wilmington Trust, National Association, as Trustee (the “Trustee”) (the “Base Indenture”) and the Second Supplemental Indenture, dated as of May 23, 2017, between the Company and the Trustee (the “Second Supplemental Indenture” and, together with the Base Indenture, the “Indenture”).

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 the Indenture and the Registration Statement on Form S-3 (Registration No. 333-218033), filed with the Securities and Exchange Commission (the “Commission”) on May 16, 2017 (the “Registration Statement”), for registration under the Securities Act of 1933 (the “Securities Act”) of an indeterminate amount of securities of the Company, to be issued from time to time by the Company. As to various questions of fact material to this opinion, we have relied upon representations of officers or directors of the Company and documents furnished to us by the Company without independent verification of their accuracy. In expressing the opinions set forth herein, 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 and that the Indenture has been duly authorized, executed and delivered by, and represents a legal, valid and binding obligation of, the Trustee.

Based on the foregoing and subject to the qualifications set forth herein, we are of opinion that when the Securities are authenticated in accordance with the provisions of the Indenture and delivered and paid for, the Securities will constitute legal, valid and binding obligations of the Company (subject to applicable bankruptcy, insolvency, reorganization, moratorium, fraudulent transfer and other similar laws affecting creditors’ rights generally from time to time in effect and to general principles of equity, including, without limitation, concepts of materiality, reasonableness, good faith and fair dealing, regardless of whether considered in a proceeding in equity or at law).

We hereby consent to the incorporation of this opinion as an exhibit to the Registration Statement. We also consent to the reference to our firm under the caption “Legal Matters” in the Prospectus Supplement dated May 17, 2017 forming a part of the Registration Statement. In giving this consent, we do not thereby admit that we are included in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission.

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 Delaware General Corporation Law and the laws of the State of New York.

Very truly yours,

/s/ Cravath, Swaine & Moore LLP

Atlas Air Worldwide Holdings, Inc.

2000 Westchester Avenue

Purchase, New York 10577-2543

O

2