He is best known as being a member of the sketch comedy team The League of Gentlemen, along with fellow performers Mark Gatiss, Reece Shearsmith, and co-writer Jeremy Dyson, all of whom he met at Bretton Hall College in his late teens. The League of Gentlemen initially began as a stage act in 1995, then transferred to BBC Radio 4 as On the Town with the League of Gentlemen in 1997, and finally arrived on television on BBC Two in 1999. The latter has seen Pemberton and his colleagues awarded a British Academy Television Award, a Royal Television Society Award, and a Golden Rose of Montreux.
2007 saw Pemberton make an appearance as a vicar in the film Mr. Bean's Holiday. In July 2007, he took over from Bob Martin as "Man in Chair" in the West End production of the musical The Drowsy Chaperone, playing the role until the production closed on 4 August 2007. In the 2008 English language DVD re-release of the cult 2006 Norwegian animated film Free Jimmy, Pemberton voiced Mattis, a heavy-set and bizarrely-dressed biker member of the Lappish Mafia. In June 2009, Psychoville aired and marked Pemberton's return to BBC Two. It was co-written by Pemberton and his fellow League of Gentlemen member Reece Shearsmith. Both of them play numerous characters in the series, similar to the format of The League of Gentlemen.