Mrdja made his debut for the Victory on 5 February 2010, coming on as a halftime substitute in a win over North Queensland Fury, in the second-last round of the 2009–10 A-League regular season. He scored his first goal for the club two weeks later, in a win in the first leg of the major semifinal against Sydney FC, before being sent off later in the match for elbowing Shannon Cole. Mrdja received a two-game suspension for the incident, which eventually saw him miss the 2010 A-League Grand Final.