FC Strombeek first registered at the Royal Belgian Football Association in 1932. After many seasons played at the lower levels of Belgian football, Strombeek first reached the third division by winning the Promotion D - Belgium's 4th highest level of football - in 1995–96. After three seasons at that level, they won the third division A in 1999–2000, gaining promotion to the second division for the first time in their history. They finished at the 10th place in the second division in 2000–01. The next season, Strombeek finished at the 9th place. At the same time, the club of RWD Molenbeek, though ranked 10th in the first division, were refused their professional license, and were subsequently relegated to the third division, struggling with financial problems. At this moment, Johan Vermeersch decicided to create another club by moving KFC Strombeek to Molenbeek, in order to play at the second level instead of the third level unless the will of the fans. Therefore, RWD Molenbeek was terminated, with KFC Strombeek moving from the Singelstadion, their stadium in Grimbergen to Molenbeek's stadium, the Stade Edmond Machtens. KFC Strombeek finished at the 9th place again in the second division in the 2002–03 season. Only 2 players from Strombeek remaining at the club, and the new club was named FC Molenbeek Brussels Strombeek, with the aim to promote to the first division the next season.
The new club won the second division right away under the coaching of Harm van Veldhoven but the manager was eventually fired in the summer. The new coach Emilio Ferrera made a bad start with the team at the highest level and was replaced by former Belgium manager Robert Waseige during the 2004–05 season. Although Waseige managed to prevent Brussels' relegation (the team finished 15th) he resigned at the end of the season. The chairman Johan Vermeersch then hired FrenchmanAlbert Cartier for the 2005–06 season. It turned out to be the club's best season as they reached their highest ranking in their history, the 10th place in the first division. At the end of a disastrous 2007–08 season, FC Brussels found themselves far adrift at the bottom of the table, 8 points behind Sint-Truidense with whom they were relegated to the second division.