Gasteyer entwickelte Comedy–Erfahrung mit der Los Angeles Impro – Sketch-Comedy-Gruppe The Groundlings. Sie spielte kleine Rollen auf Seinfeld (als verurteilter Kunde des Suppennazis) sowie in den Shows Party of Five, Frasier, Hope & Gloria und NYPD Blue. 1996 trat Gasteyer der Besetzung von Saturday Night Live bei. Zu ihren beliebtesten Figuren gehörten die Highschool-Musiklehrerin Bobbie Mohan-Culp, Margaret Jo McCullen, die Moderatorin von National Public Radio Delicious Dish, die feministische Sängerin Cinder Calhoun von Lilith Fair und ihre Eindrücke von Martha Stewart und Celine Dion. Im Jahr 2000 sprachen sie und Chris Parnell vor, um Colin Quinn als Co-Anker des Nachrichtenparodie-Segments Weekend Update zu folgen, aber die Positionen gingen schließlich an Tina Fey und Jimmy Fallon.Nach sechs Spielzeiten verließ Gasteyer SNL im Jahr 2002. Anschließend trat sie in verschiedenen Fernsehprogrammen, Filmen und Bühnenproduktionen auf. Im Jahr 2004 spielte Gasteyer die Mutter der Hauptfigur Cady Heron (Lindsay Lohan) in dem Spielfilm Mean Girls, geschrieben von SNL Castmate Tina Fey. Der Film zeigte auch andere ehemalige SNL-Castmates, darunter Fey, Tim Meadows und Amy Poehler. Sie erschien auch in der 2005 Showtime Film Musical Reefer Madness als Mae, die verdammte Freundin von Jack und Besitzer der Reefer Den.Gasteyer spielte in einer Wiederbelebung der Threepenny Opera am Broadway als Mrs. Peachum, zusammen mit Jim Dale, Alan Cumming und Cyndi Lauper. Die Produktion lief vom 24.März bis 25.Juni 2006.Am 24.Juni 2005 bekam Gasteyer die Rolle der Elphaba in der Chicago Sit-down-Produktion des Musicals Wicked, neben Kate Reinders als Glinda. Die Produktion wurde am 13.Juli 2005 eröffnet. Gasteyer wurde für ihre Leistung für einen Jefferson Award nominiert. Sie spielte ihre letzte Aufführung am 22. Januar 2006, ersetzt durch ihre Assistentin Kristy Cates. Sie wiederholte später die Rolle in der Broadway-Produktion vom 10. Oktober 2006 bis zum 7. Januar 2007 und ersetzte Eden Espinosa.Am 12. April 2007 gaben die Medien bekannt, dass Gasteyer sich der Besetzung des damals neuen Musicals Writing Arthur für das 2007 New Works Festival for TheatreWorks in Kalifornien angeschlossen hatte, das vom 14. bis 22. April stattfand. Gasteyer spielte in Chicago in der Stephen Sondheim Musical Passion am Chicago Shakespeare Theater vom 2. Oktober 2007 bis 11. November 2007.
Sie wurde ursprünglich als Gloria in den Zugaben besetzt! Sommerserienproduktion von Damn Yankees, aber aufgrund einer Verletzung während der Proben wurde sie durch Megan Lawrence ersetzt. Gasteyer nahm an der Lesung der Broadway-Musical-Version von The First Wives Club teil.Sie spielte als Kitty Dean in dem Broadway-Stück The Royal Family, das am 15. September 2009 im Samuel J. Friedman Theatre aufgeführt und am 8. Oktober 2009 offiziell eröffnet wurde. Die Show endete am 13.Dezember 2009. Gasteyer spielte auch als Frisco Kate Fothergill in den City Centers Encores! produktion von Girl Crazy, läuft vom 19. bis 22.November 2009.Sie kehrte zu Saturday Night Live für eine spezielle Muttertags-Episode am 8. Mai 2010 und für eine weitere Muttertags-Episode am 11. Mai 2012 zurück.Gasteyer erschien in der achten Staffel von Curb Your Enthusiasm als Larry Davids Freundin.Von 2011 bis 2014 spielte Gasteyer als Sheila Shay in der ABC-Comedy-Serie Suburgatory und ab März 2013 war sie Sprecherin des Weight Watchers-Diätplans.
2014 nahm Gasteyer ihre Ausbildung zur Sängerin auf und veröffentlichte I’m Hip, ein Album mit Jazzstandards. „One Mint Julep“ war eine der Auswahlen, die es enthielt. 2015 spielte sie Mimi Schwinn in den New York City Center Encores! Off-Broadway-Wiederbelebung des Musicals A New Brain, auch auf der Besetzung Aufnahme erscheinen.
Von 2016 bis 2017 hatte Gasteyer eine Hauptrolle in TBS Kulthit People of Earth, als Anführer einer Alien-Entführten-Selbsthilfegruppe.
Im Oktober 2019 veröffentlichte sie das Weihnachtsalbum Sugar & Booze. Gasteyer trat später als Kandidat in der zweiten Staffel von The Masked Singer unter dem Deckmantel von „The Tree“ auf und beendete den Wettbewerb schließlich auf dem sechsten Platz.
Im Februar 2020 wird Gasteyer die Rolle der Katherine Hastings in der NBC-Komödie Pilot American Auto spielen, die von Justin Spitzer geschrieben wurde. Im September und Oktober 2020 sprach sie einen roten Panda namens Nut in einer Zeichentrickserie für Erwachsene mit dem Titel Magical Girl Friendship Squad aus.