Milenić became politically active in 1996 as a member of the Zajedno coalition, a shaky alliance of several political parties opposed to Slobodan Milošević's administration. Although the Zajendo name ceased to be used in most municipalities after 1997, it continued to be the name of Stevanović's local political movement for several years thereafter; Milenić was a prominent member of this organization. At the republic level, both Milenić and Stevanović were initially members of the Serbian Renewal Movement. Milenić appeared on the SPO's electoral list in the 2000 Serbian parliamentary election; the list did not cross the threshold to win representation in the assembly. The SPO formed an alliance with New Serbia for the 2003 Serbian parliamentary election, and Milenić appeared in the thirty-eighth position on their list, which won twenty-two mandates. From 2000 to 2011, parliamentary mandates in Serbia were awarded at the discretion of the sponsoring parties, and it was common practice for seats to be awarded out of numerical order; the SPO could have selected Milenić for a seat in parliament, but it did not. Following local elections in 2004, he became deputy mayor of Kragujevac, a position he held for the next four years. The SPO subsequently split in 2005, and Milenić joined a breakaway group called the Serbian Democratic Renewal Movement. The party contested the 2007 Serbian parliamentary election on a list led by New Serbia and the Democratic Party of Serbia. Milenić was included on the list, which won forty-seven seats. He was again not selected for a mandate.
Stevanović and Milenić affiliated with the G17 Plus alliance after the 2007 election. This alliance participated in the 2008 Serbian parliamentary election as part of the For a European Serbia list led by the Democratic Party. The list won 102 mandates, and both Stevanović and Milenić were selected as representatives. The DS and its allies formed a coalition government after the election, and Stevanović and Milenić served in the assembly as supporters of the ministry. Both resigned in September 2011, due to a determination that changes in Serbian law had made their executive functions at the municipal level incompatible with serving in the legislature. G17 Plus and Together for Šumadija subsequently joined the United Regions of Serbia, an alliance which contested the 2012 Serbian parliamentary election on its own list. After Serbia's 2011 electoral reforms, parliamentary mandates were awarded in numerical order to candidates on successful lists. Milenić received the tenth position on the URS list and was duly re-elected when the party won sixteen mandates. After the election, the URS initially participated in a new coalition government led by the Serbian Progressive Party and the Socialist Party of Serbia; in 2013, however, it moved into opposition. In the same year, the various constituent groups of the URS merged into a single united party. Milenić was a substitute member of the Parliamentary Assembly of the Council of Europe from 21 January 2013 to 22 May 2014. He also served two terms as president of the Kragujevac assembly between 2008 and 2014; his second term in office, lasting from 2012 to 2014, ended when the Serbian Progressive Party and its allies formed a new local administration.
Since 2014
Milenić was promoted to the second position on the URS's list in the 2014 Serbian parliamentary election, but the list did not cross the threshold to win representation in the assembly. The URS subsequently dissolved, and Together for Šumadija was re-established at the local level. For the 2016 Serbian parliamentary election, Together for Šumadija joined a coalition led by the DS. Milenić received the twenty-sixth position and was not returned when the list won sixteen seats. Milenić left Together for Šumadija in 2017, saying that it had not existed as a functional political organization for some time. He joined the Movement of Free Citizens on that party's founding in the same year. In August 2019, he argued that the PSG's decision on boycotting the next Serbian parliamentary election should be made openly by the entire party rather than by its leadership alone.
