Exhibit 5.1

July 31, 2020

Southwest Airlines Co.

2702 Love Field Drive

Dallas, Texas 75235

Re: 5.250% Notes due 2025 and 5.125% Notes due 2027

Dear Ladies and Gentlemen:

We have acted as counsel for Southwest Airlines Co., a Texas corporation (the “Company”), with respect to certain legal matters in connection with the registration by the Company under the Securities Act of 1933 (the “Securities Act”) of the offer and sale by the Company of $300,000,000 aggregate principal amount of 5.250% Notes due 2025 and $700,000,000 aggregate principal amount of 5.125% Notes due 2027 (together, the “Notes”), pursuant to the Underwriting Agreement, dated July 28, 2020 (the “Underwriting Agreement”), among the Company and Goldman Sachs & Co. LLC and Wells Fargo Securities, LLC, for themselves and as representatives of the underwriters party thereto (the “Underwriters”). The 2025 Notes represent an additional issuance of the Company’s 5.250% Notes due 2025, of which the Company issued $1,250,000,000 aggregate principal amount on May 4, 2020, and the 2027 Notes represent an additional issuance of the Company’s 5.125% Notes due 2027, of which the Company issued $1,300,000,000 aggregate principal amount on June 8, 2020.

The Notes have been offered for sale pursuant to a prospectus supplement, dated July 28, 2020, filed with the Securities and Exchange Commission (the “Commission”) pursuant to Rule 424(b) on July 30, 2020, to the prospectus, dated February 9, 2018 (as amended and supplemented by the prospectus supplement, the “Prospectus”), that constitutes a part of the Company’s Registration Statement on Form S-3 (Registration No. 333-222963), filed with the Commission on February 9, 2018 (the “Registration Statement”), which Registration Statement became effective upon filing with the Commission pursuant to Rule 462(e) under the Securities Act. The Notes will be issued under an indenture, dated as of September 17, 2004, between the Company and Wells Fargo Bank, N.A., as trustee (in such capacity, the “Trustee”), as supplemented by those certain officers’ certificates of the Company, dated May 4, 2020, June 8, 2020, and July 31, 2020, establishing the terms of each series of the Notes (together, the “Indenture”).

July 31, 2020 Page 2

We have examined originals or copies, certified or otherwise identified to our satisfaction, of (i) the Company’s Restated Certificate of Formation and the Second Amended and Restated Bylaws of the Company, (ii) certain resolutions adopted by the Board of Directors of the Company relating to the Registration Statement and related matters, (iii) certain resolutions adopted by the Pricing Committee of the Board of Directors of the Company relating to the issuance and sale of the Notes, (iv) the Registration Statement, (v) the Prospectus, (vi) the Indenture and (vii) such other certificates, instruments and documents as we considered appropriate for purposes of the opinions hereafter expressed. In addition, we reviewed such questions of law as we considered appropriate.

As to any facts material to the opinions 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.

In connection with rendering the opinions 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, (v) all persons executing and delivering the documents we examined were competent to execute and deliver such documents, (vi) all Notes will be issued and sold in compliance with applicable federal and state securities laws and in the manner stated in the Prospectus and the Registration Statement (vii) the Underwriting Agreement has been duly authorized and validly executed and delivered by the Underwriters and (viii) the Indenture was duly authorized, executed, and delivered by the Trustee.

Based upon such examination and review and the assumptions, qualifications, limitations and exceptions set forth herein, we are of the opinion that the Notes have been duly authorized, executed and issued by the Company and, assuming that the Notes have been duly authenticated by the Trustee, they constitute valid and binding obligations of the Company.

This opinion is limited in all respects to the laws of the States of Texas and the federal laws of the United States of America, and we do not express any opinion as to the laws of any other jurisdiction.

This opinion letter may be filed as an exhibit to the Registration Statement. In giving this consent, we do not thereby admit that we come 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.

[Signature Page Follows]

[SIGNATURE PAGE TO 5.1 LEGAL OPINION]