The airline was established in 12 June 2000 by Capt. Sugeng Triyono and his 4 colleagues which started as helicopter charter services company with various leased helicopters. Since 2003 Aviastar began operating fix wing aircraft with 2 units of DeHavilland Canada DHC-6-300 Twin Otters and began to drop its rotary wings operations.
Aviastar now is an established company dealing with air transportation services either for chartered flights or schedule flights and currently operates 4 units of DHC-6-300 and 3 units of BAe 146-200 with plan to order 3 units more of DHC-6-300 to add in its fleet before end of 2013.
Its main operation base is located in Jakarta (CGK) with other operation bases in Palangkaraya (PKY), Balikpapan (BPN), Makassar (UPG), Nabire (NBX) and Denpasar (DPS).