With the booming of travel in the Asia region at the beginning of 2010, new airlines started appearing and establishing a mix of low cost services and full service airlines to compete in the lucrative tourism sector. This was specially higher in Malaysia, Thailand or Indonesia. The background of Malindo Air is the creation of the subsidiary airline by its parent company the Lion Air group, based in Indonesia on 26 September 2012. Before this date, the entry of AirAsia from Malaysia in the home ground of Lion Air encouraged the Indonesian airline to enter the Malaysian market with a subsidiary airline. (At the same time AirAsia's subsidiary Indonesia AirAsia, in partnership with its parent firm, attempted to buy Indonesian carrier Batavia Air to gain a better market share in Indonesia, but the deal did not go through due to regulatory complications and Batavia Air ended up going bankrupt). The attempted failed deal resulted in higher competition between Lion Air, Indonesia's biggest low-cost carrier, and AirAsia, Asia's biggest low-cost carrier. 

The Indonesian airline Lion Air, then took advantage of open market agreements between Indonesia and Malaysia, and created its own subsidiary airline based in Malaysia, named Malindo Air. The airline's inaugural flights began operations on 22 March 2013. Its first aircraft were Boeing 737-800 operated from the Parent company Lion Air. 

The airline began operating many routes in competition with other low cost airlines and traditional national carriers, but it differentiated itself by offering for its jet routes, providing a personal TV (in-flight entertainment system) in every seat, light snacks and free meals, above average legroom and free baggage allowance on most flights. The airline also took delivery of the Boeing 737-900 in March 2013, out of 6 on order which would be the initial platform of operations till more -800 version aircraft arrived the following year in 2014.

The airline also has expanded on a parallel turboprop service with ATR 72-600 which began operations in May 2013, focusing mainly on secondary routes within a 2-hour radius from Sultan Abdul Aziz Shah Airport. Pioneer destinations include Penang, Johor Bahru and Kota Bharu, which started in June 2013. In June 2015, Malindo became the first Malaysian airline to offer in-flight Wi-Fi service.

In 2016, Malindo had taken up all its Boeing 737-800 aircraft it on order. However, in early 2017, the airline took a strategic change in its operations and is expected to re-brand Malindo Air to "Batik Air Malaysia" which will focus on international routes while its associate airline, Batik Air serves domestic routes in Indonesia. The airline begun to feature the Batik Air Malaysia logo and livery on its aircraft gradually.

Malindo and Turkish Airlines  announced an interline agreement, in order to better improve connections and to enable passengers to find connections easier when travelling between ASEAN and Europe. It also started talks with Qatar Airways, to become their interline partner as well.

In April 2017, Malindo Air received its International Air Transport Association (IATA) certificate as IATA member.  Malindo Air was the world's first Boeing 737 Max 8 operator to fly a commercial flight on 22 May 2017, operating the Kuala Lumpur to Singapore route as flight OD803.The new aircraft, are configured with 180 seats in an all-economy configuration. It also feature the airline's new livery and branding. However after just 4 months the new aircraft were transferred to Lion Air (the parent company in Indonesia) and Malindo Air continued operating their own fleet of Boeing 737-800/900 aircraft and ATR 72-600 as of late 2018. 

History source: Wikipedia.org + Malindoair.com + airfleets.net