Shin második filmszerepe is Jang rendezés volt, mégpedig az 1999-ben készült vígjáték, a The Spy. Ekkoriban még „ingázott” a mozi és a színház között, hiszen olyan darabokban lépett fel a színpadon, mint a Magic Time (1998), a Vain Effort (1999) és a The Big Scene (másik címe Murder, Take one) (2000). Koreában ismert és elismert színésznek tartották már ekkoriban is, de nem tartották alkalmasnak arra, hogy egy nagy film főszereplője legyen. Amíg Lee Byung-Hun, Won Bin vagy Jang Dong-Kun a külsejükkel (is) meghóditották a koreaiakat és a nemzetközi filmvilágot, Choi Min-Shik és Song Kang-Ho híres, nagy költségvetésű filmekben nyújtott nagyszerű színészi alakításokkal tette magát ismertté, addig Shin szépen csendesen építgette karrierjét. Ugyan jópár, az előbb említett névvel szerepelt együtt több nagy filmben is, mégsem sikerült igazi nevet szereznie magának. Hozzájárult ehhez az is, hogy a többi koreai sztárral ellentétben ő alig-alig szerepelt a tévében. Nagyritkán hívták csak meg televíziós show műsorokba és mindössze egy tévésorozat fűződik a nevéhez, ráadásul már abból az időszakból, amikor kezdett túllépni ezen a „nem túl feltűnő” időszakán (ez a tévésorozat a 2003-ban forgatott Nice Guy volt egyébként).


De térjünk vissza 2000 környékére, amikor Shin még a nézőknek nem annyira szúrt szemet, azonban az egyik ismert koreai filmrendezőnek, Kim Ji-Woon-nak igen, aki hamarosan két filmjében is szerepeltette, a The Foul King-ben egy cameo szerep erejéig, a 40 perces internet filmjében, a Coming Out-ban pedig az egyik mellékszerepet osztotta rá.
Az igazi áttörést Chan-wook Park Joint Security Area című filmje hozta meg Shin számára, amiben egy fiatal észak-koreai katonát alakított. Ugyan a színészek közül ebben a filmben is inkább Song Kang-Ho és Lee Byung-hun volt leginkább reflektorfényben, de Shin  alakítását is elismerték, az addig alig ismert színész rajongótábora folyamatosan növekedett. A következő évben Jin Jang akcióvígjátékában, a Guns & Talks-ban szerepelt, ami az első könnyed hangvételű, igazi közönségfilmje volt.
2002-től kezdve egyre több filmszerepet kapott, de mindenképpen megemlítendő, hogy Jan Jing színházi művében, a három évvel később megfilmesített Welcome to Dongmakgol-ban is ekkoriban játszott. Chan-wook Park bosszútrilógiájának első részében, a Sympathy for Mr. Vengeance-ben egy süketnéma, furcsa frizurájú emberrablót játszott, a Jin Jang forgatókönyvéből készített No Comment főszerepét is ő kapta, valamint a Surprise Party című romantikus vígjátékban is meghatározó szerepe volt. Ez utóbbi film nem lett túlzottan sikeres, akárcsak a nem sokkal ezután bemutatott Save the Green Planet!, amiben Shin egy tébolyultnak tűnő fiatalt alakított, aki a barátnőjével együtt úgy hiszi, a hogy a Földet földönkívüliek inváziója fenyegeti, akik az Andromeda-ról származnak. A filmet a kritikák dícsérték, viszont odahaza a mozikban megbukott, azonban nyugaton (főleg az Egyesült Államokban) hamar „underground” kultfilm lett belőle. Akárcsak a korábbi filmjeiben, Shin ebben a filmben is hiába játszott nagyszerűen, továbbra sem szúrt igazán szemet senkinek sem, a történet mellett másodlagos volt mindenki számára a színészek személye. 2003-ban még egy filmben játszott főszerepet, mégpedig az A Letter from Mars-ban, ami a címével ellentétben nem sci-fi, hanem egy romantikus dráma volt, Shin partnerét Hee-seon Kim játszotta benne.


2004-ben a két testvér történetét feldolgozó My Brother-ben alakította Sung-hyun szerepét Won Bin mellett, valamint szerepet kapott a Hair címet viselő rövidfilmben is. Egy évvel később Chan-Wook Park egy cameo szerep erejéig szerződtette bosszútrilógiájának harmadik részére, a Sympathy for Lady Vengeance-re, ebben egy jelenet erejéig egy bérgyilkost játszott. Ugyancsak ebben az évben egy újabb híres film, a Jin Jang színpadi drámájából adaptált Welcome to Dongmakgol egyik főszerepében volt látható, mégpedig a JSA-val ellentétben ezúttal egy dél-koreai katona szerepét alakította. Jin Jang másik színpadi művéből maga Jin Jang készített filmet, ez volt a Murder, Take One, aminek egyik szerepét természetesen Shin-re osztotta, akinek a címben szereplő gyilkosság egyik gyanúsítottját kellett eljátszania, akit nemcsak a rendőrség, hanem a média is árgus szemekkel figyel.
Shin Ha-Kyun eddigi legújabb filmje a No Mercy for the Rude, amiben a Sympathy for Mr. Vengeance süketnéma figurája után egy újabb hasonló adottságokkal rendelkező karaktert alakít, igaz, jóval „menőbb” formában.