They finished as runners-up of the Serbian League West for the second consecutive time in 2004–05, earning a spot in the promotion play-offs.

The club subsequently defeated Železničar Niš and Radnički Obrenovac to qualify for the Serbian First League, reaching the second tier for the first time in history.

[1] Following two moderate seasons in 2006–07 and 2007–08, the club brought back Stamenković as manager and went on to finish as runners-up in the 2008–09 Serbian Cup.

They managed to upset Red Star Belgrade in the semi-final, but eventually lost 3–0 to Partizan in the final.

[2] As a result, the club automatically earned a spot in the 2009–10 UEFA Europa League, gaining the license despite competing in the second tier of Serbian football.