През сезон 2003 – 04, отбора печели [[Сръбската лига на Белград]] без загуба. На следващия сезон играе в [[Перва лига на Сърбия по футбол|Сръбска суперлига]].
През сезон 2005/06 отбора печели 3-ето местомясто в [[Шампионата на Сърбия и Черна гора по футбол 2005/2006|шампионат на Сърбия и Черна гора]], но се отказва от участие в [[Купата на УЕФА 2005/2006|Купа на УЕФА]]. През следващата година клубът попада в [[Шампионат на Сърбия по футбол|Сръбска суперлига]]. После тригодишна борба в Сръбската лига на Белград, през сезон 2011/12 печели първото място и се завръща в първа лига на Сърбия. Там той веднага заема трето място. И след отказа на „[[ФК Хайдук (Кула)|Хайдук (Кула)]]“, „Вождовац“ заема вакантното място и през 2013/14 участва в Сръбската суперлига. В тоя сезоне отбора заема уверено 7-то място, което е най-доброто им класиране в [[Шампионат на Сърбия по футбол|Сръбска суперлига]]. През сезон 2015/16 отбора заема 12-то местомясто.
