Flemyng åpnet skuespillerkarrieren med å spille gjesteroller i en rekke TV-serier, som for eksempel The Young Indiana Jones Chronicles (1992). Hans første store filmrolle var som Lt. John Wilkins i The Jungle Book (1994), en versjon av Disney-filmen med samme navn, bare i levende bilder. I 1998 fikk han sitt gjennombrudd som skuespiller, med rollen som Tom i kultfilmen Lock, Stock and Two Smoking Barrels. Guy Ritchie var tydeligvis så fornøyd med innsatsen hans at han to år senere brukte Flemyng igjen, denne gangen som Darren i storfilmen Snatch (2000), som også hadde folk som Brad Pitt, Benicio Del Toro og Jason Statham på rollelisten. Begge disse filmene ble skamrost av et samlet pressekorps.
Året etter var han med i krimfilmen From Hell med Johnny Depp. I 2003 spilte han en av hovedrollene i fantasyfilmen The League of Extraordinary Gentlemen, som samlet en rekke av fiksjonshistoriens mest kjente karakterer. Her spilte han Henry Jekyll/Edward Hyde. Sean Connery hadde hovedrollen i denne filmen, som ikke fikk fullt så mye ros av hverken publikum eller presse.
.jpg)
