Many of the writers were fans of Mel Brooks, and Matt Groening described the chance to have him guest star as "an incredible honor".
Susan Sarandon had wanted to guest star on the show because her children were big fans; she brought them with her to the recording session
Mel Brooks' wife Anne Bancroft had played a role in Fear of Flying (1994) and Brooks had accompanied her to the recording session.
David Mirkin realized that Mel Brooks was "dying to do the show" and asked him if he would be willing to do a guest part, and he agreed.
The Mel Brooks bit in the episode is actually called "The 2000-year-old Man". (Homer calls it "2000-Pound Man", and Wiggum calls it "$2000 Man".)