Exhibit 5.1

November 5, 2015

Southwest Airlines Co.

2702 Love Field Drive

Dallas, Texas 75235

Re: 2.650% Notes Due 2020

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 $500,000,000 principal amount of 2.650% Notes Due 2020 (the “Notes”), pursuant to the Underwriting Agreement, dated November 2, 2015 (the “Underwriting Agreement”), among the Company and Citigroup Global Markets Inc. and Merrill Lynch, Pierce, Fenner & Smith Incorporated, for themselves and as representatives of the underwriters party thereto (the “Underwriters”).

The Notes have been offered for sale pursuant to a prospectus supplement, dated November 2, 2015, filed with the Securities and Exchange Commission (the “Commission”) pursuant to Rule 424(b) on November 3, 2015, to the Prospectus dated April 30, 2015 (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. No. 333-203761), filed with the Commission on April 30, 2015 (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, National Association, as trustee (in such capacity, the “Trustee”), as supplemented by that certain officers’ certificate of the Company dated November 5, 2015 establishing the terms of the Notes (together, the “Indenture”).

We have examined originals or copies, certified or otherwise identified to our satisfaction, of (i) the Company’s Restated Certificate of Formation, as amended, and the Amended and Restated Bylaws of the Company, (ii) certain resolutions adopted by the Board of Directors of the Company relating to the terms and sale of the Notes and related matters, (iii) certain resolutions adopted by the Pricing Committee of the Board of Directors of the Company, (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.

November 5, 2015   Page 2

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.