Frank Caliendo syntyi Chicagossa, Illinoississa ja kasvoi Waukeshassa, Wisconsinssa. Caliendo aloitti esiintymisensä stand-up-koomikkona paikallisella komediaklubilla. Hänen tv-debyyttinsä oli vuosina 2000–2001 sketsikomedia-sarjassa Hype. Sen jälkeen hän on tehnyt monia stand-up -esiintymisiä televisio-ohjelmissa, esimerkiksi Late Show with David Lettermanissa ja Late Night with Conan O'Brienissa.