On February 6, 2013, Vranješ signed a two-year contract with Serbian giants FK Vojvodina. He cemented his place in Vojvodina's starting XI under coach Nebojša Vignjević and gradually adopted the role as a trequartista with his silky dribbling and passing game. He scored his first goal for Vojvodina in a 2-1 win against FK Smederevo on February 27, 2013. He scored an impressive goal from distance in a 3-0 win against FK Donji Srem on March 19, 2013, which local media dubbed a "euro-goal". Even with the arrival of new coach Marko Nikolić, Vranješ kept his starting place in spite of turbulent administrative changes that were taking place in FK Vojvodina.