The club become notable for having Bulgaria's prime minister, Boyko Borisov, as a registered player of the squad. The increased popularity of the club due to Borisov's presence led to its coach and players being featured on the TV series BNT Taxi in 2011.
The club was founded in 1958 and played in the regional divisions until 2007, when it gained promotion to the third division. In the 1972–73 Bulgarian Cup they entered the Preliminary round, losing by Pirin Blagoevgrad with the 3:0 result.
2007–2016: Amateur division and B Group breakthrough
From 2007 the team were playing in the V Group. Its highest finish to was achieved during the 2010–11 season, when the club finished third in the final ranking. In May 2012, Vitosha claimed the Amateur League Cup for the first time in its history, defeating Dve Mogili 2–1 in the final. During the 2012-13 season, the club finished second in the South-West V Group and achieved promotion to Bulgaria's professional B Group for the first time in the club's history.
In the 2013–14 Bulgarian Cup, Vitosha eliminated Bansko with an aggregate score of 3-1 to advance to the Round of 16 of the Bulgarian Cup for the first time ever in the club's history. Previously, their highest achievement had been reaching the Round of 32 in the 1972 Bulgarian Cup.
2016–present: Professional league and academy development
Vitosha finished 2015–16 V Group season on 2nd position after CSKA Sofia and due to Second League expanding were promoted again to Second Division.  The team started investing in the youth team having 5 youth teams for the 2016–17 season and renovated the club stadium. On 3 May 2017 the team announced an update of their logo, looking after not only about infrastructure plan, but also about their image.  On 8 May 2017 Vitosha signed with Efbet to be the new general team sponsor.