The company started flight operations on the Tokyo-Sapporo route, using the Air Do brand, in December 1998. Its first CEO was the former Japan manager of Virgin Atlantic Airways. Maintenance and ground handling services were outsourced to Japan Airlines. Air Do enjoyed very high load factors during its first few months of operation, as its fares were 60% to 70% of the walk-up fares offered by established airlines.
However, other airlines quickly adopted their own discounted advance purchase fares in the wake of Air Do's initial success, driving load factors down to around 50%. The Hokkaido prefectural government injected more capital in 2000 and installed one of its senior officials as head of the company. After being harder hit financially in the aftermath of the September 11, 2001 attacks, and being denied additional financing from the Hokkaido prefectural government, Air Do entered Japanese corporate restructuring procedures in June 2002.
Air Do received new equity capital from a tokumei kumiai investment fund arranged by the Development Bank of Japan, in which All Nippon Airways was a key investor. This began a number of business relationships between Air Do and ANA, including ANA code sharing on Air Do operated flights and Air Do leasing additional 767 and 737 aircraft from ANA. The fund was dissolved in September 2008 and DBJ, ANA and other investors became direct shareholders in Air Do.
The company officially changed its name to Air Do in October 2012.