Né Melvin Kaminsky d'une famille juive allemande - russe à Brooklyn (New York), le 28 juin 1926. Après avoir servi dans l'armée de terre lors de la Seconde Guerre mondiale, il travaille comme standup comic.
Avec Woody Allen, Neil Simon et d'autres, il écrit pour le Sid Caesar's Your Show of Shows, lequel devient le Caesar's Hour. Mel Brooks et Buck Henry travaillent ensemble pour créer à la télévision la parodie d'espionnage Max la Menace (Get Smart) diffusée de 1965 à 1970, avec Don Adams.
Durant cette époque, il est producteur de théâtre, épouse en 1964 l'actrice Anne Bancroft (avec qui il aura un fils Max en 1972, et restera marié jusqu'au décès d'Anne Bancroft en 2005) et réalise son premier film : un court-métrage parodique sur l'art moderne intitulé The Critic, film qui remporte un Oscar. Il écrit ensuite un scénario fondé sur son expérience avec les producteurs de Broadway, qui devient son premier long métrage en tant que réalisateur :
Les Producteurs (The Producers). C'est là qu'il fait la connaissance de l'acteur qui deviendra son coéquipier dans bon nombre de ses films, Gene Wilder. Lors de la sortie de son deuxième long métrage en 1970, Le Mystère des douze chaises (The Twelve Chairs), Hollywood critique le film comme étant trop juif. En 1974, alors qu'il est en train de tourner un de ses plus célèbres films,
Le Shérif est en prison, Gene Wilder lui propose un scénario original. Il s'agit alors de Frankenstein Junior, une parodie du grand film des années 1930, qui deviendra par la suite son film le plus célèbre, avec Les Producteurs. Le rôle d'Igor est alors joué par Marty Feldman. Le reste de la troupe sera constitué de Teri Garr, Cloris Leachman, Peter Boyle (apparaissant quelques années plus tard aux côtés de Robert DeNiro dans Taxi Driver) et on peut même apercevoir Gene Hackman dans le rôle de l'ermite aveugle. En 1981, Mel est à l'origine d'un des premiers morceaux de rap de l'histoire intitulé "It's good to be the king" ("c'est bon d'être le roi") où il apparait déguisé en Louis XVI dans le clip. "It's good to be the king" sera un tube planétaire qui fera danser des millions de personnes à travers le monde. En fait pour ce rap, il reprend le rôle de Louis XVI qu'il tenait dans son propre film La Folle Histoire du monde et dont il reprend sa phrase fétiche: "C'est bon d'être le roi". Mel récidivera avec d'autres morceaux rap comme "Inquisition" sans toutefois connaître un succès comparable à "It's good to be the king"... Travaillant simultanément comme scénariste, metteur en scène et acteur, Mel Brooks obtint beaucoup de mauvaises critiques dues à son style excessif. En 1983, aux côtés d'Anne Bancroft, il est seulement acteur lors du remake du classique d'Ernst Lubitsch, To Be or Not to Be. Au cours des années 1980, il continue de travailler au sein de sa société de production Brooksfilms comme producteur pour des projets aussi variés que La Mouche (The Fly),
Elephant Man, Solarbabies, et 84 Charing Cross Road mettant en vedette Anne Bancroft.
En 1991, il fait une tentative de film non-parodique avec
Chienne de vie (Life Stinks), mais le film est un échec. Il revient alors à son domaine de prédilection, les parodies avec Sacré Robin des Bois (Robin Hood : Men in Tights) et Dracula, mort et heureux de l'être (Dracula: Dead and Loving it). Mel Brooks passe la deuxième moitié des années 1990 à jouer le rôle d'Oncle Phil dans la série télévisée Dingue de toi sur NBC. En 2001, la version théâtrale des Producteurs, avec Nathan Lane et Matthew Broderick, connaît un triomphe et bat un record en remportant un Grammy et douze Tony Awards mais aussi un oscar et un Emmy.
Le 23 avril 2010, il reçut la 2406ème étoile du Hollywood Walk of Fame.