Exhibit 5.1

Tel +1.214.220.7700   Fax +1.214.220.7716

July 28, 2023

Southwest Airlines Co.

P.O. Box 36611

Dallas, Texas 75235

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 certain selling security holders from time to time, pursuant to Rule 415 under the Securities Act, of (1) warrants of the Company (the “Warrants”), to purchase shares of common stock, par value $1.00 per share, of the Company (“Common Stock” and, together with the Warrants, the “Securities”), and (2) shares of Common Stock issuable upon exercise of the Warrants. The Company has advised us that the Securities will be offered by the selling security holders in amounts, at prices and on terms to be determined in light of market conditions at the time of sale and to be set forth in supplements to the prospectus contained in the Company’s Registration Statement on Form S-3 (the “Registration Statement”) to which this opinion is an exhibit.

We have examined originals or copies, certified or otherwise identified to our satisfaction, of (1) the Restated Certificate of Formation, the Second Amended and Restated Bylaws of the Company, effective as of November 17, 2016, and the Third Amended and Restated Bylaws of the Company, effective as of February 1, 2023; (2) resolutions adopted by the Board of Directors of the Company (the Board of Directors, or to the extent permitted by Section 21.416 of the Texas Business Organizations Code, a duly constituted and acting committee thereof, being referred to herein as the “Board”); (3) the Registration Statement; and (4) such other certificates, statutes and other 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 deemed such reliance proper, upon certificates of public officials and officers or other representatives of the Company.

In rendering the opinions set forth below, we have assumed that (1) all information contained in all documents reviewed by us is true and correct; (2) all signatures on all documents examined by us are genuine; (3) all documents submitted to us as originals are authentic and all documents submitted to us as copies conform to the originals of those documents; (4) each natural person signing any document reviewed by us had the legal capacity to do so; (5) each person signing in a representative capacity (other than on behalf of the Company) any document reviewed by us had authority to sign in such capacity; (6) the Registration Statement, and any post-effective amendments thereto, will be effective and comply with all applicable laws; (7) one or more

Vinson & Elkins LLP Attorneys at Law Austin     Dallas     Dubai     Houston     London     Los Angeles New York     Richmond     San Francisco     Tokyo     Washington Trammell Crow Center, 2001 Ross Avenue, Suite 3900
Dallas, TX 75201-2975 Tel   +1.214.220.7700   Fax +1.214.220.7716 velaw.com

Southwest Airlines Co.        July 28, 2023        Page 2

prospectus supplements will have been prepared and filed with the Securities and Exchange Commission describing the Securities offered thereby; (8) all Securities will be issued and sold in compliance with applicable federal and state securities laws and in the manner stated in the Registration Statement and an applicable prospectus supplement; and (9) a definitive purchase, underwriting or similar agreement and any other necessary agreement with respect to any Securities offered (including a warrant agreement) will have been duly authorized and validly executed and delivered by the selling security holders and the other parties thereto.

Based on the foregoing, and subject to the assumptions, qualifications, limitations and exceptions set forth herein, we are of the opinion that:

(1)    With respect to the Warrants, when (i) the Board has taken all necessary corporate action to approve the creation of and the issuance and terms of the Warrants, the terms of the offering thereof and related matters; (ii) the warrant agreement or agreements relating to the Warrants have been duly authorized and validly executed and delivered by the Company and the warrant agent appointed by the Company; and (iii) the Warrants or certificates representing the Warrants have been duly executed, countersigned, registered and delivered in accordance with the appropriate warrant agreement or agreements and the applicable definitive purchase, underwriting or similar agreement approved by the Board upon payment of the consideration therefor provided for therein, the Warrants will be legally issued and will constitute valid and binding obligations of the Company.

(2)    With respect to shares of Common Stock issuable pursuant to Warrants, when (i) the Board has taken all necessary corporate action to approve the issuance and terms of the offering thereof and related matters; and (ii) certificates representing the shares of Common Stock have been duly executed, countersigned, registered and delivered (or non-certificated shares of Common Stock have been properly delivered) upon exercise of any such Warrants in accordance with the terms of the Warrants and any applicable warrant agreement providing for the exercise as approved by the Board, then upon payment of the consideration approved by the Board (not less than the par value of the Common Stock), such shares of Common Stock will be validly issued, fully paid and non-assessable.

The foregoing opinions are qualified to the extent that the enforceability of the Warrants may be limited by or subject to bankruptcy, insolvency, fraudulent transfer or conveyance, reorganization, moratorium or other similar laws relating to or affecting creditors’ rights generally, and general equitable or public policy principles (regardless of whether enforcement is sought in a proceeding in equity or law).

The foregoing opinions are limited in all respects to the laws of the State of Texas and the federal laws of the United States of America, and we do not express any opinions as to the laws of any other jurisdiction.

Southwest Airlines Co.        July 28, 2023        Page 3

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the use of our name in the prospectus forming a part of the Registration Statement under the caption “Legal Matters.” By giving such consent, we do not 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 Securities and Exchange Commission issued thereunder.

Very truly yours,

/s/ Vinson & Elkins LLP