On returning to England, Cleese landed a job writing for TV's "The Frost Report". He and Chapman collaborated on several screenplays and teleplays (the pilot episode of the TV series, "Doctor in the House"; additional material for "The Magic Christian" 1970; "The Rise and Rise of Michael Rimmer" 1970) roughly contemporaneous with the formation of Monty Python's Flying Circus for BBC TV. Possibly the best-known of the Pythons, Cleese also enjoyed considerable success with a more conventional but nonetheless uproarious sitcom "Fawlty Towers" (BBC-2, 1975; BBC-2, 1979), co-written by Booth. Here he portrayed Basil Fawlty, the perpetually frustrated owner of a resort inn, as sort of a middle-class Ralph Kramden on the verge of a nervous breakdown. Cleese was also the co-founder of Video Arts Ltd., a company specializing in witty training films in which he often starred and which has become the largest training film company in the world outside the USA. Cleese also acted in and co-wrote all the Monty Python features and has appeared in films by Python alumni Terry Jones and Gilliam.

Cleese acted in a number of non-Python-related British comedies in the 80s (e.g., "Privates on Parade" 1982; "Yellowbeard" 1983; "Clockwise" 1986). He has also become a familiar face in American TV commercials and in small memorable turns in Hollywood features (i.e., "The Great Muppet Caper" 1981; Lawrence Kasdan's "Silverado" 1985; "The Big Picture" 1989; and voice work for the animated "An American Tail: Fieval Goes West" 1991). Cleese's greatest film success was "A Fish Called Wanda" (1988), a blockbuster comedy directed by Ealing Studio veteran Charles Crichton and starring Cleese (as an uptight British barrister), Jamie Lee Curtis (a sexy con artist), Kevin Kline (her macho boyfriend) and former Python Michael Palin (as a hilariously tortured animal lover). Having written the screenplay, he also served as executive producer, and the little gem that cost slightly more than $7 million to make took in more than $200 million. He later appeared to less success with Idle and Rick Moranis in "Splitting Heirs" (1993), a strained comedy in the Monty Python tradition which failed to deliver the requisite laughs.

The success of "A Fish Called Wanda" cried out for a sequel, and Cleese, his apoplectic zoo director recalling Basil Fawlty, reunited with his "Wanda" co-stars for "Fierce Creatures" (1997), a pleasant enough farce but hardly the "equal" of "Wanda". The year before had provided a little seen gem reuniting four of the original six Python members (Idle, Cleese, Jones, Palin), Terry Jones' live-action take on Kenneth Grahame's 1908 classic "The Wind in the Willows". The ensemble including Steve Coogan and Nicol Williamson ably tackled its animal story for children and adult satire of British class pretensions, but despite rave reviews, Columbia Pictures declined to promote it, having received its distribution rights (but not its video rights) as part of an arbitrated award in a lawsuit with Disney. Cleese, who can still be seen in the occasional commercial, had a banner year in 1999, playing an obnoxious hotel clerk with a penchant for women's clothes in the remake of "The Out-of-Towners" and Simon & Schuster head Dick Snyder in the Jacqueline Susann biopic "Isn't She Great", not to mention taking his first turn on Her Majesty's Secret Service as R, the apprentice gadget-master to Q (Desmond Llewelyn) in a James Bond pic, "The World Is Not Enough", featuring cameos from more than a dozen glamorous Bond girls from pictures past.

In 2002, Cleese may have intially smarted from his ratings-impaired and critically drubbed sitcom "Wednesday at 9:30 (8:30 Central)" and an appearence in one of the year's biggest bombs, "The Adventures of Pluto Nash," but he ended the year on a triumphant high note with two hugely popular films. He portrayed Nearly Headless Nick in "Harry Potter and the Chamber of Secrets" (2002), a character that he first introduced in "Harry Potter and the Sorcerer's Stone" (2001). He was then seen in the James Bond action feature "Die Another Day"(2002), his second Bond movie and the first in the role of Q (with the passing of Llewelyn). This time around Cleese brought even more of his trademark cheek and disdain to the part. The comedian's talents were woefully underused in his turn as Lucy Liu's staid father in "Charlie's Angels 2: Full Throttle" (2003), in a thin, juvenile "Three's Company"-style subplot in the otherwise fun romp. In 2003 Cleese joined the cast of NBC's hit sit-com "Will & Grace" in a delightful recurring role as Lyle "Finney" Finster, the paramour of Karen Walker (Megan Mullally) and the father of Karen's arch-nemesis (Minnie Driver). The actor also lent his haughty tones to the voice of King Harold, father of Princess Fiona (Cameron Diaz) in the CGI sequel "Shrek 2" (2004).

Cleese and the other surviving members of the Python troupe gave their blessing to Eric Idle's Broadway production of "Spamalot," a stage musical drawn from their 1975 film "Monty Python and the Holy Grail." The 2005 debut earned rave reviews and broke box office records, and although Cleese did not appear in person, he was the only Python in the cast as he provided the voice of God for the original production.

A longtime outspoken advocate and activist for animals, Cleese inspired researchers in 2005 to name a newly discovered species of Madagascar lemur after him: the avahi cleesei.