Born in East Harlem, Pellegrino has often acted in law and gangster-themed film and television productions. He was a member of an early 1960s singing group called the Holidaes. There is a rare recording of a song called "Never" that appears on FOUND IN THE BASEMENT VOL. 1. Notable roles of his include Johnny Dio in GoodFellas, assorted appearances on Law & Order, and FBI Chief Frank Cubitoso on The Sopranos.
Pellegrino is a co-owner of the restaurant Rao's in New York City. Books written by Pellegrino include Rao's Cookbook,Rao's Recipes from the Neighborhood and Rao's on the Grill. He also produced the CD An Evening at Rao's, featuring music from Rao's jukebox.
Frank Pellegrino sings on the "Heavenly Lullabies" Cd with Dr. Kathy Reilly Fallon which was dedicated to the Babies & Orphans of 9-11-01. He is co-author and sings on "Heavenly Skies & Lullabies Illustrated Song Book & Cd" with Dr. Kathy Reilly Fallon. These two projects were produced by Heavenly Productions Foundation, a 501c-3 not for profit charity based in Armonk, New York that help children in need and in distress.