Legend's initial flights were substantially delayed by lobbying to persuade Congress to modify the Wright Amendment, court battles instigated by American Airlines and the city of Fort Worth, and by difficulties obtaining operational approval from the Federal Aviation Administration (FAA).

The airline's private Love Field terminal—which was independently owned and leased to the carrier—was condemned under eminent domain and the gates razed after the 2006 Wright Amendment repeal imposed a 20-gate cap at the airport.

By the early 1960s, Love Field was reaching the limits of its capacity, and efforts to share Greater Southwest International Airport (GSW) in Fort Worth had proven unsuccessful.

[11][12] By July 1997, McArtor had enlisted the help of Senator Richard Shelby of Alabama, who proposed to change the Wright restrictions to allow Legend to use reconfigured aircraft.

[12] In October 1998, Legend sued Fort Worth, accusing the city of a "double standard" in its simultaneous support for Alliance and opposition to expansion at Love.

[20] However, State District Judge Bob McCoy dismissed the suit later that month on the grounds that Legend was not a party to the 1968 DFW bond agreement and thus lacked standing to sue.

[21] On 5 April 2000, after further legal battles against Fort Worth and American Airlines and delays in gaining operating approval from the FAA, Legend began the first long-haul service from Love Field since 1974 with a flight to Washington Dulles International Airport (IAD).

[3][30] In May, McArtor left Legend to head the North American unit of Airbus, and the airline's physical assets were auctioned in June 2001, including an estimated $1 million in DC-9 spares, but not the aircraft themselves, which were leased.

Legend's activities prompted other aviation interests to seriously consider using regional jets on long-haul flights from Love Field and to more openly back changes to the Wright Amendment, ideas that seemed infeasible beforehand.

[34] The terminal cost $20 million to construct and reflected the airline's upscale image, with leather seats, fresh flowers, and gates designed to resemble private executive clubs.

[38] In late 2005, the owners were publicly backing an effort to repeal the Wright Amendment, hoping to boost the lease value of the still-vacant gates; however, Dallas mayor Laura Miller was openly campaigning for the structure to be torn down.

Among other provisions, the agreement imposed a permanent 20-gate cap at Love Field and obligated Dallas to revise its airport master plan and demolish all gates in excess of that number "as soon as practical".

[40][41] After the partial repeal of the Wright Amendment became effective in October 2006, the Dallas City Council immediately approved using eminent domain to seize and raze the Legend gates to comply with the cap.

[42] This effectively ended negotiations to sell the facility to Pinnacle Airlines, and the gates were subsequently condemned by the federal government and torn down, with the owners receiving nothing in return.