He has periodically returned to theatrical work, appearing in several productions. In 2003, he appeared as Bernard in a run of David Mamet's play "Sexual Perversity in Chicago", along with Matthew Perry and Minnie Driver, in London's West End. Azaria made his first appearance as Sir Lancelot, the French Taunter, and four other characters in "Spamalot", the musical version of "Monty Python and the Holy Grail", which opened in Chicago in December 2004, before moving to the Shubert Theatre on Broadway. The show met with critical acclaim, receiving fourteen Tony Award nominations in 2005, with Azaria being nominated for Best Performance by a Leading Actor in a Musical. Reuniting with "The Birdcage" director Mike Nichols, and being a huge "Monty Python" fan, he saw it as an opportunity he could not pass up, describing it as "so much fun that I haven't realized how tiring it is," and "the most fun that I've ever had in my entire life." He took a break from the show in June 2005, with Alan Tudyk filling in for him, to work on "Huff", but returned in December 2005. In late 2007 he starred in Aaron Sorkin's "The Farnsworth Invention", playing RCA head David Sarnoff. In 2016, he starred in the world premiere of "Dry Powder" opposite Claire Danes, John Krasinski, and Sanjit De Silva, directed by Thomas Kail, at the off-Broadway Public Theater in New York City.