Prije bosanskohercegovačke A selekcije igrao je za bosanskohercegovačka mladu U-21 reprezentaciju.
Za A reprezentaciju debitovao je 13. oktobra 2007. godine u kvalifikacionoj utakmici za Evropsko prvenstvo protiv reprezentacije Grčke.
Svoj prvi gol u dresu reprezentacije postigao je iz slobodnog udarca 9. juna 2009. godine na prijateljskoj utakmici protiv reprezentacije Omana u Cannesu.
U junu 2014. godine, Salihović je pozvan da nastupi za BIH na Svjetskom prvenstvu u Brazilu. Tokom grupne faze prvenstva, Salihović bilježi dva nastupa kao zamjena, ali uspijeva upisati jednu asistenciju u pobijedi BIH protiv Irana rezultatom 3-1.
Nakon prelaska u kineski klub Guzhou Renhe u 2015. godini, Salihović postaje povremeni reprezentativac BIH.
Datum | Domacin | Rezultat | Gost | Min |  / / | Video |
13/10/2007 | Greece | 3 : 2 | BIH | 8' |  | |
17/10/2007 | BIH | 0 : 2 | Norway | 90' | 37' | |
21/11/2007 | Turkey | 1 : 0 | BIH | 7' | | |
26/03/2008 | BIH | 2 : 2 | Macedonia | 13' | | |
06/09/2008 | Spain | 1 : 0 | BIH | 90' | | |
10/09/2008 | BIH | 7 : 0 | Estonia | 90' | | |
11/10/2008 | Turkey | 2 : 1 | BIH | 90' | | |
15/10/2008 | BIH | 4 : 1 | Armenia | 90' | | |
19/11/2008 | Slovenia | 3 : 4 | BIH | 72' | 53' | |
09/06/2009 | Oman | 1 : 2 | BIH | 90' | 84' | |
12/08/2009 | BIH | 2 : 3 | Iran | 90' | | |
05/09/2009 | Armenia | 0 : 2 | BIH | 90' | | |
09/09/2009 | BIH | 1 : 1 | Turkey | 90' | 25' | |
10/10/2009 | Estonia | 0 : 2 | BIH | 90' | | |
14/10/2009 | BIH | 2 : 5 | Spain | 73' | | |
14/11/2009 | Portugal | 1 : 0 | BIH | 90' | | |
18/11/2009 | BIH | 0 : 1 | Portugal | 76' | 76' | |
03/03/2010 | BIH | 2 : 1 | Ghana | 90' | | |
29/05/2010 | Sweden | 4 : 2 | BIH | 90' | 46' | |
03/06/2010 | Germany | 3 : 1 | BIH | 78' | | |
17/11/2010 | Slovakia | 2 : 3 | BIH | 64' | | |
09/02/2011 | Mexico | 2 : 0 | BIH | 77' | | |
10/08/2011 | BIH | 0 : 0 | Greece | 60' | | |
02/09/2011 | Belarus | 0 : 2 | BIH | 72' | 21' | |
06/09/2011 | BIH | 1 : 0 | Belarus | 20' | 9' | |
11/11/2011 | BIH | 0 : 0 | Portugal | 67' | 17' | |
28/02/2012 | Brazil | 2 : 1 | BIH | 12' | | |
15/08/2012 | Wales | 0 : 0 | BIH | 90' | | |
07/09/2012 | Liechtenstein | 1 : 8 | BIH | 90' | | |
11/09/2012 | BIH | 4 : 1 | Latvia | 90' | | |
12/10/2012 | Greece | 0 : 0 | BIH | 90' | | |
16/10/2012 | BIH | 3 : 0 | Lithuania | 90' | | |
14/11/2012 | Alžir | 0 : 1 | BIH | 90' | | |
07/06/2013 | Latvia | 0 : 5 | BIH | 75' | | |
14/08/2013 | BIH | 3 : 4 | USA | 46' | | |
06/09/2013 | BIH | 0 : 1 | Slovakia | 90' | | |
10/09/2013 | Slovakia | 1 : 2 | BIH | 69' | | |
11/10/2013 | BIH | 4 : 1 | Liechtenstein | 90' | | |
15/10/2013 | Lithuania | 0 : 1 | BIH | 90' | | |
05/03/2014 | BIH | 0 : 2 | Egypt | 90' | | |
30/05/2014 | BIH | 2 : 1 | O. Slonovače | 71' | | |
04/06/2014 | Mexico | 0 : 1 | BIH | 90' | | |
22/06/2014 | Nigeria | 1:0 | BIH | 32 | | |
25/06/2014 | BIH | 3 : 1 | Iran | 11' | | |
04/09/2014 | BIH | 3 : 0 | Liechtenstein | 90' | | |
10/10/2015 | BIH | 2 : 0 | Wales | 90' | | |
13/10/2015 | Cyprus | 2 : 3 | BIH | 5' | |
