The airline was founded in 2002, when a group of Belgian investors (companies, financial institutions and regional investment companies, as well as the Brussels and Walloon governments), set up SN Airholding, headed by Etienne Davignon. After the 2001 collapse of Sabena, Belgium's flag carrier airline, Belgium was left without a national airline. In February 2002, SN Airholding took over the Belgian airline DAT, a subsidiary of Sabena and changed its trading name to SN Brussels Airlines. In 2002, a strategic reorganization started, led by the former CEO Peter Davies. On 12 April 2005 SN Brussels took holding control of Virgin Express and on 31 March 2006 they announced their merger. On 7 November 2006 they announced at a press conference held at Brussels Airport that the new airline would be called Brussels Airlines.
The airline had various color schemes before finally settling on a uniform scheme for the fleet. The upper fuselage is white, while the belly and engines were painted lilac. An orange cheat line runs between the white and lilac parts of the fuselage. The tail shows the old Sabena "S". The website address is near the end of the fuselage. There are differences in livery between the Avro planes and the Airbus planes: most notably, the company name is written on the white part of the fuselage for the Airbus planes, but on the lilac part on the Avro.