Urodził się w Toledo[3] w stanie Ohio jako syn Alice Birdene (z domu McDonald) i Williama Alexandra Halla, pracownika fabryki z Montgomery w stanie Alabama[4]. Jego rodzina miała korzenie angielskie, niemieckie i irlandzkie[5]. Uczęszczał na Uniwersytet w Toledo[6].
Dostał role drugoplanowe w filmach takich jak komedia kryminalna Martina BrestaZdążyć przed północą (1988) i zagrał szybko mówiącego porucznika Joe Bookmana w odcinku trzeciego sezonu sitcomu NBCKroniki Seinfelda (1991, 1998). Ale to jego współpraca z reżyserem Paulem Thomasem Andersonem sprawiła, że Hall stał się popularnym i powszechnie rozpoznawalnym aktorem[10]. Począwszy od krótkometrażowego filmu Andersona Coffee & Cigarettes (1992), który później został przekształcony w pełnometrażowy dramat kryminalny Sydney (1996), gdzie zagrał tytułową rolę, za którą zdobył nominację do Independent Spirit Awards[11]. Hall wystąpił w kilku innych filmach reżysera, m.in. w Boogie Nights (1997) a przede wszystkim Magnolia (1999)[12]. Od tego czasu Hall był rozchwytywany jako aktor charakterystyczny, trafiając do wielkich filmów, takich jak Informator (1999), Suma wszystkich lęków (2002), Bruce Wszechmogący (2003) i Zodiak (2007). Za rolę Russa McDonalda w sitcomie FoxLoop (2006–2007) otrzymał nominację do Nagrody Satelity[13].
Hall miał dwie córki, Patricię i Darcy, ze swoją pierwszą żoną, Mary-Ellą Holst. Ożenił się z Holly Wolfle i miał dwie córki, Adellę i Annę[14].