Flemyng was born in Putney, London, the son of Scottish film director Gordon Flemyng. He decided he wanted to become an actor after appearing in theatrical productions at his school. "I always wanted to be an actor," he later told the BBC. "From the time I fancied a girl who played Dorothy in the school production of The Wizard of Oz. I auditioned for the role of the scarecrow so that I could have the most stage time with her, but she ended up running off with the tin man!"

In the 1980s he was involved with the National Youth Theatre and the political organisation the Young Socialists. He also became involved with the Labour Party's Militant tendency, and was expelled from Labour in 1987 for selling the Militant newspaper.

Flemyng has subsequently claimed that both his theatrical and political activities at this time were simply a way of meeting girls. In 1990 he was admitted to the London Academy of Music and Dramatic Art (LAMDA), where he was a classmate of Hermione Norris. Following his graduation from LAMDA in the early 1990s he joined the Royal Shakespeare Company.

One of his first prominent roles on screen was a guest appearance in the American television series The Young Indiana Jones Chronicles in 1992. He was then a regular in the ITV drama series Doctor Finlay from 1993 to 1996.

His first film appearance was in the 1994 version of The Jungle Book. His first major cinema role was in Guy Ritchie's 1998 London gangster film Lock, Stock and Two Smoking Barrels. Flemyng later claimed to have lost so much money while playing poker with the film's backers in between takes on set that he had to work on the four days of re-shoots the film required for no fee.

He went on to appear in films such as The Red Violin (1998), Snatch (2000), George A. Romero's Bruiser (2000) and Rock Star (2001). Flemyng also starred in the short film Feeling Good, written by Dexter Fletcher, whom he met while working on Lock, Stock and Two Smoking Barrels.

In the early 2000s he featured in two big-budget Hollywood films which were adaptations of Alan Moore comic books; as John Netley in 2001's From Hell, with Johnny Depp, and 2003's The League of Extraordinary Gentlemen, with Sean Connery, in which Flemyng played Dr. Henry Jekyll and Edward Hyde.

The latter film was not a success, but Flemyng commented that, "It was a bit of a nightmare... the film cost a fortune and didn't make back the money it was meant to... But I still get a huge kick out of doing films like that and From Hell. Any day you walk onto a set and Sean Connery or Johnny Depp or Brad Pitt is there has to be a good day."

In parallel with his film career, Flemyng has continued to take various television roles. He told BBC News Online in 2004 that: "Of the 40 feature films I've made, 15 of them failed to make it onto the screen and have only ever been seen by cast and crew. It is very frustrating when a film you really believe in remains unseen. That's not a problem with television. If you're a painter you don't paint a picture and then stick it under the bed - you want people to see it."

In 2005 he played the famous science-fiction role of Professor Bernard Quatermass when digital television channel BBC Four produced a live remake of the 1953 serial The Quatermass Experiment. In 2005 he also played the part of Dimitry, a Russian ex-biological weapons specialist, in Transporter 2.