Southwest Airlines was originally incorporated to serve three cities in Texas as Air Southwest on March 15, 1967, by Rollin King and Herb Kelleher. According to frequently-cited story, King described the concept to Kelleher over dinner by drawing on a paper napkin a triangle symbolizing the routes (Dallas, Houston, San Antonio).

Some of the incumbent airlines of the time (Braniff, Aloha Airlines, United Airlines, Trans-Texas, and Continental Airlines) initiated legal action, and thus began a three-year legal battle to keep Air Southwest on the ground. Air Southwest eventually prevailed in the Texas Supreme Court, which ultimately upheld Air Southwest’s right to fly in Texas. The decision became final on December 7, 1970, when the U.S. Supreme Court declined to review the case without comment.  

The story of Southwest’s legal fight was turned into a children’s book, Gumwrappers and Goggles by Winifred Barnum in 1983. In the story, TJ Love, a small jet, is taken to court by two larger jets to keep him from their hangar, and then to try and stop him from flying at all. Taken to court, TJ Love’s right to fly is upheld after an impassioned plea from The Lawyer. While no company names are mentioned in the book, TJ Love’s colors are those of Southwest Airlines, and the two other jets are colored in Braniff and Continental’s colors. The Lawyer is designed to resemble Herb Kelleher. The book was adapted into a stage musical, Show Your Spirit, sponsored by Southwest Airlines, and played only in towns serviced by the airline.  

Southwest Airlines founder Herb Kelleher studied California-based Pacific Southwest Airlines extensively and used many of the airline’s ideas to form the corporate culture at Southwest, and even on early flights used the same "Long Legs And Short Nights" theme for stewardesses on board typical Southwest Airlines flights. The original flight attendants that worked for Southwest Airlines were chosen by a committee of individuals that included the same person who had selected hostess for Hugh Hefner’s Playboy jet. The selection resulted in a group of female flight attendants that were described as long-legged dancers, majorettes, and cheerleaders with "unique personalities". Southwest Airlines and Herb Kelleher proceeded to dress these individuals in hot pants and go-go boots.  

The airline adopted the first profit-sharing plan in the U.S. airline industry in 1971. Through this plan and others, employees own about 10 percent of the company stock. The airline is about 87 percent unionized. The pilots are represented by the Southwest Airlines Pilots’ Association, a union separate from the much larger Air Line Pilots Association.