Op 7 juli 2011 maakte Valjić zijn debuut in Europees verband tijdens een wedstrijd tussen FC Milsami en Dinamo Tbilisi in de voorronde van de UEFA Europa League; het eindigde in 1–3 voor de bezoekers en Valjić gaf negen gele kaarten, waarvan twee aan één en dezelfde speler.[1] Zijn eerste interland floot hij op 29 februari 2012, toen Montenegro met 2–1 won van IJsland. Tijdens dit duel gaf Valjić twee gele kaarten.[2]