Op 10 augustus 2013 leidde Šehović zijn eerste wedstrijd in de Bosnische nationale competitie. Tijdens het duel tussen Velež Mostar en Leotar Trebinje (3–0 voor de thuisploeg) trok de leidsman zesmaal de gele kaart.[2] In Europees verband debuteerde hij op 19 juli 2018 tijdens een wedstrijd tussen Sjachtjor Salihorsk en Connah's Quay Nomads in de eerste voorronde van de UEFA Europa League; het eindigde in 2–0 en Šehović trok zesmaal de gele en eenmaal de rode kaart.[3] Zijn eerste interland floot hij op 7 oktober 2020, toen Montenegro met 1–1 gelijkspeelde tegen Letland door doelpunten van Igors Tarasovs en Igor Ivanović. Tijdens deze wedstrijd deelde Šehović vier keer geel uit.[4]