Poleksić speelde één interland voor Joegoslavië, het latere Servië en Montenegro. Onder leiding van bondscoach Dejan Savićević viel hij op woensdag 8 mei2002 in de 90ste minuut in voor Dragoslav Jevrić in de oefeninterland tegen Ecuador (1-0). Na de ontmanteling van Servië en Montenegro vertegenwoordigde hij Montenegro. Hij maakte zijn debuut voor de nationale ploeg op 24 maart2007 in de vriendschappelijke thuiswedstrijd tegen Hongarije, die met 2-1 werd gewonnen door Montenegro dankzij rake strafschoppen van achtereenvolgens Mirko Vučinić en Igor Burzanović. Het duel was het eerste duel voor de voormalige Joegoslavische deelrepubliek als zelfstandige staat. Poleksić verloor zijn basisplaats gaandeweg aan Mladen Božović.