Dzieciństwo i młodość spędził na nowojorskim Brooklynie. Jego rodzice - Harold Williams Sr. i Lucy Perrineau - nigdy nie wzięli ślubu, dlatego aktor używał w młodości zamiennie obu nazwisk Perrineau i Willams. Przy wpisie do gildii aktorskiej zdecydował się jednak na nazwisko Perrineau, gdyż był już jeden Harold Williams.

Studiował muzykę i teatr w Shenandoah Conservatory.

Przed kamerami zadebiutował w 1980 roku występując jako tancerz w „Sławie” Alana Parkera. Opowieści o uczniach szkoły artystycznej, ich sukcesach i porażkach. Dwa lata później został zaangażowany do serialu telewizyjnego o tym samym tytule Victora Frencha i Waltera C. Millera, który powstał na podstawie filmu.

Następnie pojawił się między innymi jako Tommie w „Błękitnym gliniarzu” (1988) Jamesa Glickenhausa, przywódca bandy w „Królu Nowgo Jorku” (1990) Abla Ferrary, Thomas Cole w „Dymie” (1995) Wayne’a Wanga i Paula Austera, a także jako Henry w filmie Boba Rafelsona „Krew i wino” (1996).

Jedną z najbardziej popularnych produkcji w jakiej wziął udział był film „Romeo i Julia” (1996) Buza Luhrmana. Ekranizacja dramatu Shakeseara z oryginalnymi dialogami i współczesną scenografią. Role tytułowe zagrali Leonardo DiCaprio i Claire Danes. Harold Perrineau wcielił się w postać Merkucja.

Później grał jeszcze między innymi Stephena w „Lekcji przetrwania” (1997) Lee Tamahori, Ariela w „Burzy” (1998) Jacka Bendera (kolejna przeróbka Shakespeara), mężczyznę w kawiarni w „Lulu na moście” (1998) Paula Austera, Juliana Murcha w „Drużbie” (1999) Malcolma D. Lee oraz Monicę Jones w „Kobiecie na topie” (2000) Finy Torres.

Rok 2003 należał w karierze Harolda Perrineau do „Matrixów”. Najpierw premierę miał „Matrix Reaktywacja”, a następnie „Matrix Rewolucje” braci Wachowskich. W obu tych filmach Perrineau zagrał Linka.

„Zagubieni” (2004 - 2007) to kolejny projekt, w którym wziął udział i kolejny spektakularny sukces. Serial otrzymał w 2006 roku nagrody Złodego Globu i Saturna dla najlepszego serialu dramatycznego. Opowiada losy ludzi, którzy ocaleli po katastrofie samolotu pasażerskiego i znaleźli się na tajemniczej wyspie. Harolda Perrineau kreował tam postać Michaela Dawsona.

Prywatnie od 2002 roku jest mężem Brittany Perrineau – modelki i aktorki, z którą ma córkę Aurorę Robinson Perrineau.