Née en Floride d'un père producteur de musique et d'une mère chanteuse de soul, Maya Rudolph fait des études de photographie et s'adonne à la musique avant de se consacrer au cinéma. Elle décroche alors de petits rôles dans Bienvenue à Gattaca (1997) aux côtés d'Ethan Hawke, Pour le pire et pour le meilleur (id.) non loin de Jack Nicholson puis dans Chuck & Buck (2000). Ses véritables débuts sur grand écran sont plus tardifs, sous la houlette de Bruce Paltrow, père de son amie d'enfance Gwyneth Paltrow, dans Duos d'un jour (2000). La même année, l'actrice rejoint le casting de l'émission phare Saturday night live de NBC où elle s'illustre notamment par ses imitations parodiques de la diva de la mode, Donatella Versace.

Elle privilégie alors le registre comique comme dans 1 duplex pour 3 (2003) de Danny DeVito, où elle donne la réplique à Ben Stiller et Drew Barrymore, puis dans Amour et amnésie (2004) où elle joue de nouveau aux côtés de l'actrice ainsi que d'Adam Sandler. Compagne du réalisateur Paul Thomas Anderson (Magnolia, Punch-drunk love - Ivre d'amour, There Will Be Blood), Maya Rudolph met un temps sa carrière entre parenthèses et donne naissance à leur premier enfant en 2005.

L'année suivante, la comédienne retrouve la musique et les performances collectives dans le musical The Last Show, dernier film du cinéaste Robert Altman, décédé la même année. La jeune femme s'essaie également à l'art du doublage en prêtant sa voix à Rapunzel dans Shrek le troisième (2007), avant d'être la tête d'affiche du road-movie Away We Go (2009) de Sam Mendes, où, enceinte, elle décide avec son compagnon (joué par John Krasinski) de traverser les Etats-Unis à la recherche de l'endroit parfait pour fonder une famille.

Juste après avoir donné naissance à son deuxième enfant, elle revient sur les écrans en tant que femme de Chris Rock dans Copains pour toujours (2010) (qui marque ses retrouvailles avec Adam Sandler) où des amis d'enfance goûtent à nouveau aux joies de leur jeunesse le temps d'un weekend. L'année d'après, Maya Rudolph est au casting de deux comédies américaines : elle interprète une jeune femme qui confie à sa meilleure amie son enterrement de vie de jeune fille dans Mes meilleures amies, et prête sa voix à une girafe dans Zookeeper.

Tout en continuant son travail dans Saturday Night Live, Maya Rudolph est, depuis 2011, Ava, l'un des personnages principaux de la série Up All Night. 2012 est ensuite pour elle l'année qui lui permet de retrouver Kristen Wiig, sa copine de Mes meilleures amies, à l'affiche de la comédie Friends With Kids de Jennifer Westfeldt.