Kolašinac speelde in diverse Duitse jeugdelftallen. Op 7 november 2013 werd hij opgeroepen voor het voetbalelftal van Bosnië en Herzegovina voor een oefeninterland tegen Argentinië op 18 november 2013. Hij kreeg van bondscoach Safet Sušić een basisplaats in die wedstrijd en speelde de gehele wedstrijd uit. Bosnië verloor het duel met 2–0 door twee doelpunten van spits Kun Agüero. Sušić nam Kolašinac in juni 2014 op in de selectie voor het wereldkampioenschap voetbal 2014, de eerste deelname van Bosnië en Herzegovina aan een eindtoernooi.[1]Op het toernooi maakte hij in de openingswedstrijd tegen latere finalist Argentinië (2–1 verlies) in de derde minuut een eigen doelpunt, het snelste eigen doelpunt in de geschiedenis van het wereldkampioenschap voetbal.[2] Ook in de afsluitende groepswedstrijd tegen Iran op 25 juni 2014 speelde Kolašinac mee; Bosnië en Herzegovina won met 3–1, maar overleefde de groepsfase niet.