The airline was established on November 27, 1995 as East Line Air, that later on February 8, 1996 was granted Certificate No 61 by the civil aviation authorities of Russia. This Certificate had entitled the airline to operate all types of domestic civil aircraft. From January 3, 1996, East Line Air became a member of IATA. In 1997 the airline was renamed East Line Airlines, and a new Operator’s Certificate, retaining the same number, was approved on 4 September 1997, and subsequently renewed in compliance with the Federal Aviation Authorities regulations. East Line Airlines was a part of East Line group, which owns Domodedovo airport. They also were one of the leading cargo carriers in Russia.
In May 2004 a change of shareholders of East Line Airlines took place. The Extraordinary Meeting of Shareholders of East Line Airlines, held on June 7, 2004, resolved to delegate the authority of a sole executive body to a Managing Organization — Russian Sky Aviation Group, and on October 21, 2004 East Line Airlines was renamed Russian Sky Airlines without any change of the legal entity.