Paula Robison was born in Nashville, Tennessee, the daughter of David V. and Naomi Robison, an actor. David Robison was a musicologist who later became a playwright and a film and television writer. Her paternal grandmother was a piano teacher, her maternal uncle the playwright Jerome Lawrence, and there were other musicians and dancers in the family. David studied in Vienna, and upon his return joined the faculty of Fisk University. There the family met the singer Paul Robeson, who became Paula's godfather. The entire family was immersed in the arts, leftward-leaning political beliefs, and the beginnings of the civil rights movement.