United Airlines traces its claim to be the oldest commercial airline in the United States to the Varney Airlines air mail service of Walter Varney, who also founded Continental Airlines. It was founded in Boise, Idaho. Varney's chief pilot, Leon D. "Lee" Cuddeback, flew the first Contract Air Mail flight in a Swallow biplane from Varney's headquarters in Boise, Idaho to the railroad mail hub at Pasco, Washington on April 6, 1926, and returned the following day with 200 pounds of mail. April 6 is regarded in the United Airlines company history as both its own birthday and the date on which "true" airline service—operating on fixed routes and fixed schedules—began in the United States. Varney Airlines' original 1925 hangar served as a portion of the terminal building for the Boise Airport until 2003, when the structure was replaced.  

In 1927, airplane pioneer William Boeing founded his own airline, Boeing Air Transport, and began buying other airmail carriers, including Varney's. Within four years, Boeing's holdings grew to include airlines, airplane and parts manufacturing companies, and several airports. In 1929, the company changed its name to United Aircraft and Transport Corp. (UATC). In 1930, as the capacity of airplanes proved sufficient to carry not only mail but also passengers, Boeing Air Transport hired a registered nurse, Ellen Church, to assist passengers. United claims Church as the first airline stewardess. On May 7, 1930, UATC completed the acquisition of National Air Transport Inc, a large carrier based in Chicago. 

On March 28, 1931, UATC formed the corporation United Air Lines, Inc. to manage the UATC airline subsidiaries. Following the Air Mail scandal of 1930, the Air Mail Act of 1934 banned the common ownership of manufacturers and airlines. UATC's President Philip G. Johnson was forced to resign and moved to Trans-Canada Airlines, the future Air Canada. William Boeing's company was broken into three: a parts supplier (the future United Technologies), an aircraft manufacturer (the Boeing Airplane Company), and the United Air Lines airline group. The airline company's new president, hired to make a fresh start as airmail contracts were re-awarded in 1934, was William A. Patterson, who remained as president of United Airlines until 1963. 

United had begun to seek overseas routes in the 1960s, but the Transpacific Route Case (1969) denied them this expansion. It did not gain an overseas route until 1983, when they began flights to Tokyo from Portland and Seattle. In 1985, United agreed to purchase Pan American World Airways' entire Pacific Division, Boeing 747SPs, and L-1011-500s for $750 million. By the end of 1986, United operated flights to 13 Pacific destinations, most of which were purchased from the ailing Pan American World Airways. Economic turmoil, labor unrest, and the pressures of the 1978 Airline Deregulation Act greatly affected the company, which incurred losses and saw a greatly increased turnover in its senior management through the 1970s and early 1980s.  In May 1981, one week after rival American Airlines launched AAdvantage, the first modern frequent flyer program, United launched its Mileage Plus. In 1982, United became the launch carrier for the Boeing 767, taking its first delivery of 767-200s on August 19. In 1984, United became the first airline to serve all 50 states when it introduced service to Atlanta, Nashville, Memphis, Little Rock, Fargo, Casper, Jackson, and Charleston. 

On May 17, 1985, United's pilots went on a 29-day strike claiming the CEO, Richard Ferris, was trying to "break the unions." They used management's proposed "B-scale" pilot pay rates as proof. American Airlines already had a non-merging B-scale for its pilots. Ferris insisted United had to have pilot costs no higher than American's, so he offered United pilots a "word-for-word" contract to match American's, or the same bottom line numbers. The United ALPA-MEC rejected that offer. The only choice left, to achieve parity with American's pilot costs, was to begin a B-scale for United's new-hire pilots. Ferris wanted that B-scale to merge in the captain's ranks, which was more generous than American's B-scale, that never merged at all. But, the ALPA MEC insisted they merge in the new pilot's sixth-year with the airline. In the final hours before the strike, nearly all issues had been resolved, except for the time length of the B-scale. 

It appeared that would be resolved too as negotiations continued. ALPA negotiators delivered a new counter-proposal at 12:20 A.M. in an effort to avoid the strike. However, MEC Chairman Roger Hall, who was hosting a national teleconference from the Odeum (a convention center in the Chicago suburbs) with F. Lee Bailey, declared the strike was on at 12:01 A.M., on May 17, without further consulting the negotiators, some of whom believed they could find agreement on all contract terms, if the negotiations were allowed to continue. Moments before the ALPA announced strike deadline, they began a "countdown of the final 30 seconds from Chicago" (the Odeum teleconference). Doing that made it impossible to extend the strike deadline, so that the final issues could be resolved without a strike. 

Mr. Ferris changed United's parent company's name from UAL Corporation to Allegis in February, 1987 but the name change was short lived. Following Ferris' termination by the board, Allegis divested its non-airline properties in 1987 and reverted to the name UAL Corp. in May 1988.