Medojević komt uit de jeugdopleiding van FK Vojvodina. Hij debuteerde tijdens het seizoen 2006/07 op 2 mei 2007 tegen FK Mladost Apatin. Hij speelde 68 competitiewedstrijden voor FK Vojvodina, waarin hij vijf keer scoorde. Medojević tekende op 2 januari 2012 een contract bij het Duitse VfL Wolfsburg, dat €2.000.000,- voor hem betaalde. Hij debuteerde voor VfL Wolfsburg op 31 maart 2012 tegen FC Nürnberg.