Excelente actor que ha trabajado en teatro, cine y televisión, se ha ganada la bien merecida fama de actor dispuesto a interpretar cualquier papel.

Actualmente está trabajando en el teatro en la obra de Suzan Lori Parks ganadora del premio Pulitzer Topdog/Underdog, dirigida por Geoge Wolf en el Seattle Repertory Theatre. Topdog/Underdog es la historia de dos hermanos de sangre - Lincoln (Perrineau), tahúr e imitador de Abraham Lincoln, y Booth (Larry Gilliard Jr.), aprendiz del timo de las tres cartas. The Seattle Times calificó la interpretación de Perrineau de "fascinante... su interpretación de una melodía de blues morbosamente triste es un momento álgido triste y divertido a la vez". También intervendrá en dicha obra en San Francisco del 5 de octubre al 16 de noviembre, y en Los Angeles durante los meses de febrero y marzo de 2004.

Además de su papel en Matrix Reloaded, Perrineau ha intervenido recientemente en Woman on Top junto a Penélope Cruz. También intervino en El mejor amigo del novio de Malcolm D. Lee, junto a Taye Diggs y Nia Long. Por este papel fue nominado para un premio Image como "mejor actor secundario en una película". Además, Perrineau recibió el premio Independent Spirit como "mejor actor secundario" por su interpretación de Rashid Cole en la aclamada película de Wayne Wang Smoke.

Entre sus restantes trabajos en cine figuran Romeo y Julieta de William Shakespeare de Baz Luhrmann, Lulu On The Bridge de Auster, The Edge de Lee Tamahori, junto a Anthony Hopkins y Alec Baldwin, entre otras muchas.

En televisión, Perrineau es conocido por su papel de Augustus Hill, confinado a una silla de ruedas, en el aclamado drama carcelario de la HBO OZ creado por Tom Fontana. Entre sus restantes trabajos en televisión figuran: la película de la semana de la NBC An American Tempest, así como papeles en Dead Like Me, Urgencias, Ley y orden, The Cosby Show, y I'll Fly Away, elogiada por la crítica.

Perrineau comenzó su carrera en el teatro, interviniendo en una serie de obras como Dreamgirls, Avenue X, la reposición en el Off-Broadway de Godspell y The Love of Bullets en el Public Theater. Más recientemente, obtuvo excelentes críticas por Blue/Orange de Joe Penhall, en la que interpretaba el papel de un joven al que diagnostican un trastorno de personalidad.
Perrineau, que nació en Brooklyn, estudió música y teatro en el Shenandoah Conservatory. También estudió con una beca en la Alvin Ailey Company.