Shehi speelde in de jeugd van Teuta Durrës, voor wie hij in het seizoen 1994/95 ook zijn debuut zou maken. Na drie jaar minder dan tien wedstrijden per jaargang te hebben gespeeld, kwam de doelman in het seizoen 1997/98 tot tweeëndertig competitieoptredens. Het jaar erna bracht hij door op huurbasis bij Bylis Ballsh. Met die club bereikte Shehi Europees voetbal door derde te eindigen in de Kategoria Superiore. Na zijn terugkeer bij Teuta Durrës speelde Shehi nog vier seizoenen voor die club, voor hij de overstap maakte naar Vllaznia Shkodër, waarvoor hij iets langer dan een jaar zou uitkomen. De doelman verkaste in de zomer van 2005 naar Partizan Tirana. Drie jaar later zou hij bij deze club de aanvoerdersband om zijn arm gaan dragen. Een jaar na het krijgen van de band, verliet hij Tirana om te gaan spelen voor Besa Kavajë. Met die club won Shehi voor de tweede keer in zijn carrière de beker, die hij eerder al op zijn naam mocht zetten als speler van Teuta Durrës. In de zomer van 2010 maakte hij de overstap naar Skënderbeu Korçë. Skënderbeu werd na zijn komst zesmaal op rij landskampioen. In het seizoen 2014/15 tekende Shehi voor zijn allereerste doelpunt als voetballer. Op 6 december 2014 speelde Skënderbeu tegen de club waar de doelman zijn carrière begon: Teuta Durrës. Na eenenveertig minuten legde scheidsrechter Lorenc Jemini de bal op de strafschopstip. Shehi besloot de strafschop te nemen en hij scoorde, waarmee hij de score opende. Uiteindelijk won Skënderbeu het duel met 3–2.[1] In de zomer van 2018 zette Shehi een punt achter zijn actieve loopbaan.
Shehi maakte zijn debuut in het Albanees voetbalelftal op 17 november 2010, toen met 0–0 gelijkgespeeld werd tegen Macedonië. Hij moest van bondscoach Josip Kuže op de reservebank beginnen. Na de rust kwam hij het veld op als vervanger van Samir Ujkani. De andere debutanten dit duel waren Ledian Memushaj (Chievo Verona) en Ahmed Januzi (Vorskla Poltava).[2] Met Albanië nam Shehi in juni 2016 deel aan het Europees kampioenschap voetbal 2016. Albanië werd in de groepsfase uitgeschakeld, nadat het in Groep A op de derde plek eindigde achter Frankrijk en Zwitserland. Shehi kwam op het EK in geen van de drie groepsduels in actie.
.svg){kind=small}
Albanië
Teuta Durrës
Georgië – Albanië 
Qatar – Albanië 
San Marino – Albanië 
Kosovo – Albanië 
Luxemburg – Albanië