The roots of the airline can be traced back to February 1927, when an Aeroflot department serving the Makhachkala region of the Soviet Union was founded. In 1994, following the split-up of Aeroflot, it became and independent company known as Makhachkala Air Enterprise. In 1996, the company was rebranded as Dagestan Airlines. In March 2007, it had 809 employees.
From 2010 onwards, the South East Airlines branding was introduced. On 19 December 2011, the airline had its licence revoked.