Pena was born in Hyannis, Massachusetts. Pena spoke Cape Verdean Creole with his family while growing up. His grandfather, Francisco Pena, and father, Joaquim "Jack" Pena, were both professional musicians, and taught Paul to play Cape Verdean music.