คอลาชินัตส์ถือหนังสือเดินทางเยอรมนี เขาจึงได้ลงเล่นให้กับทีมชาติเยอรมนีหลายรุ่นอายุ ต่อมาเขาย้ายไปเล่นให้กับทีมชาติบอสเนียและเฮอร์เซโกวีนา ซึ่งเป็นทีมชาติบ้านเกิดของพ่อและแม่ คอลาชินัตส์ถูกเรียกตัวติดทีมชาติในปี ค.ศ. 2013. พ่อของเขากล่าวว่า การเลือกเล่นให้ทีมชาติบอสเนีย เป็นตัวเลือกแรกของคอลาชินัตส์[11]

วันที่ 18 พฤศจิกายน ค.ศ. 2013 คอลาชินัตส์ลงเล่นให้บอสเนียนัดแรก เป็นนัดกระชับมิตรที่แพ้อาร์เจนตินา 2–0[12] ต่อมาเขามีชื่อติดทีมชาติไปแข่งขันฟุตบอลโลก 2014 ที่ประเทศบราซิล[13] ในนาทีที่ 3 ของการแข่งขันนัดแรกของกลุ่ม คอลาชินัตส์สกัดเข้าประตูตัวเองอย่างโชคร้าย ในนัดที่แพ้อาร์เจนตินา 2–1 ที่สนามกีฬามารากานัง ถือเป็นการทำเข้าประตูตัวเองที่เร็วที่สุดในประวัติศาสตร์ฟุตบอลโลก[14]