The first recorded aircraft to land at what is now Sultan Muhammad Salahuddin Airport was a Vickers Vimy on 9 December 1919, piloted by Captain Ross Macpherson Smith alongside his brother, Lieutenant Keith Macpherson Smith, as part of their historic 1919 England–Australia flight from London to Darwin. The aircraft made a brief stop in Bima to refuel, with fuel supplied by the Bataafse Petroleum Maatschappij (BPM), before continuing to Kupang and ultimately Australia. In 1920, another notable aviator, John Cowe McIntosh, also carried out an emergency landing at Palibelo when his aircraft was forced to refuel in Bima. The selection of Palibelo by the Smith brothers was not coincidental, as the site proved to be strategically important from an aeronautical perspective. In the years that followed, several prominent aviators used the location as a stopover. Among them was Amy Johnson, who in 1930 became the first woman to fly solo from England to Australia and also stopped at Palibelo for refueling. Amy Johnson’s visit coincided with the birth of the fifth daughter of Sultan Muhammad Salahuddin. Inspired by her achievements as a pioneering female aviator, the Sultan named his daughter Amy.

Further development of Bima Airport began after it was used as a landing ground during the 1920 “Great Britain” air race. In 1927, formal measurements of the runway were conducted, and it has since reached a length of 1,647 meters. By the 1930s, a small commercial airport had been established at the site, operated by KLM. Initially, the airport had only a simple runway made of woven bamboo. During the Pacific War in World War II, the airfield was used by the Royal Australian Air Force (RAAF) as a transit and refueling point after it joined Allied operations in the campaign against Japan.

Following the end of the war, the airport was handed over to the newly independent Indonesian government and began serving commercial flights. In the 1960s, Zamrud Aviation Corporation introduced a route connecting Bima and Makassar, which operated for several years before being discontinued. In 1962, Merpati Nusantara Airlines also launched services on the same route, maintaining operations until the 1980s. Decades later, Sabang Merauke Raya Air Charter (SMAC) revived the Bima–Makassar route in 2011 using a CASA C-212 Aviocar, albeit with a stopover in Selayar. Merpati Nusantara Airlines briefly reinstated the route in early 2012 with a Xian MA-60, but the service ended in February 2014 when the airline ceased operations. At present, the Bima–Makassar route is served exclusively by Wings Air.