Millennium Airlines was incorporated in July 2004 as Deccan Aviation Lanka, a private helicopter operator in partnership between Deccan Aviation of India and the Favourite Group of Sri Lanka. By early 2007 the company started fixed-wing charter operations with the introduction of a fleet of Beechcraft 1900 aircraft.
Millennium Airlines (Formerly Deccan Aviation Lanka) provides air taxi services to the tourism industry based in Colombo. In January 2008, Millennium Airlines launched an airborne medical evacuation service. In May 2011, it introduced the eight seater Gippsland GA8 aircraft and expanded its fleet with the addition of the Cessna T206H amphibious aircraft in December 2012
Deccan Aviation (India), now known as Deccan Charters Ltd, exited from the company in November 2011, after selling their equity to Singapore-based Millennium Aero Pte. Ltd, which prompted the company to rebrand as "Simplifly" with effect from 2013.