Exhibit 5.1

Tel +1.713.758.2222 Fax +1.713.758.2346

April 26, 2012

Southwest Airlines Co.

2702 Love Field Drive

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, as amended (the “Securities Act”), of the offer and sale by the Company from time to time, pursuant to Rule 415 under the Securities Act, of (1) unsecured debt securities of the Company (“Debt Securities”), in one or more series, consisting of notes, debentures or other evidences of indebtedness and which may be convertible into shares of common stock, par value $1.00 per share, of the Company (“Common Stock,” and together with the Debt Securities, the “Securities”), and (2) shares of Common Stock. The Company has advised us that the Securities will be offered 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 Articles of Incorporation and the Amended and Restated Bylaws of the Company, each as amended to the date hereof; (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; (4) the Indenture between the Company and Wells Fargo Bank, N.A., as trustee, dated September 17, 2004 (the “Indenture”) relating to the Debt Securities; and (5) 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.

Vinson & Elkins LLP Attorneys at Law Abu Dhabi Austin Beijing Dallas Dubai Hong Kong Houston London Moscow New York Palo Alto Riyadh Shanghai Tokyo Washington First City Tower, 1001 Fannin Street, Suite 2500 Houston, TX 77002-6760 Tel +1.713.758.2222 Fax +1.713.758.2346 www.velaw.com

Southwest Airlines Co.        April 26, 2012        Page 2

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 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; (9) the Indenture has been duly authorized, executed and delivered by the Trustee, and any supplemental indenture to the Indenture or other instruments establishing a series of Debt Securities to be issued under the Indenture will be duly authorized, executed and delivered by the parties thereto in substantially the form reviewed by us or with changes that do not affect the opinions given hereunder; (10) at the time of any offering or sale of any shares of Common Stock, that the Company will have at least such number of shares of Common Stock authorized, created and, if appropriate, reserved for issuance; (11) a definitive purchase, underwriting or similar agreement with respect to any Securities offered will have been duly authorized and validly executed and delivered by the Company and the other parties thereto; and (12) any shares of Common Stock issuable upon conversion of any Debt Security being offered and sold will at the time of such offering or sale have been duly authorized and, if appropriate, reserved for issue upon such conversion.

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 Debt Securities to be issued under the Indenture, when (a) the Indenture has been duly qualified under the Trust Indenture Act of 1939; (b) the Board has taken all necessary corporate action to approve the issuance and terms of such Debt Securities, the terms of the offering thereof and related matters; (c) the terms of such Debt Securities and of their issuance and sale have been established so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company or any of its assets or properties and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company or any of its assets or properties; and (d) such Debt Securities have been duly executed, authenticated, issued and delivered in accordance with the provisions of the Indenture and in accordance with the applicable definitive purchase, underwriting or similar agreement approved by the Board, then upon payment of the consideration provided for therein, such Debt Securities will be legally issued and will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms and will be entitled to the benefits of the Indenture.

Southwest Airlines Co.        April 26, 2012        Page 3

(2) With respect to shares of Common Stock, when (a) the Board has taken all necessary corporate action to approve the issuance and terms of the offering thereof and related matters; and (b) 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 issued) in accordance with the applicable definitive purchase, underwriting or similar agreement approved by the Board, then upon payment of the consideration therefor (not less than the par value of the Common Stock) provided for therein, 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 Indenture or any Debt Security may be limited by or subject to (1) 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), and (2) with respect to any Debt Securities denominated in a currency other than United States dollars, the requirement that a claim (or a foreign currency judgment in respect of such a claim) with respect to such Debt Securities be converted to United States dollars at a rate of exchange prevailing on a date determined pursuant to applicable law or governmental authority.

We express no opinions concerning (1) the validity or enforceability of any provisions contained in the Indenture that purport to waive or not give effect to rights to notices, defenses, subrogation or other rights or benefits that cannot be effectively waived under applicable law or (2) the enforceability of indemnification provisions to the extent they purport to relate to liabilities resulting from or based upon any violation of federal or state securities or blue sky laws.

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.

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 L.L.P.