Après avoir obtenu en 1978 un master en science criminelle à l'Université de Brockport dans l'état de New York, William Edward "Bill" Fichtner décide d'étudier la comédie à l'Académie d'Art dramatique de New York. Il débute sa carrière dans le soap-opera As the World Turns en 1987. L'acteur y reste jusqu'en 1993 tout en obtenant parallèlement des petits rôles au cinéma.
Tout au long de sa carrière, William Fichtner participe à de grosses productions hollywoodiennes, telles que Strange Days (1996), Contact (1997), Armageddon (1998), En pleine tempête (2000) ou encore Pearl Harbor (2001). Il ne néglige pas pour autant les projets de cinéastes artistiquement plus ambitieux, dont Michael Mann (Heat, 1996), Steven Soderbergh (A fleur de peau, id.), Ridley Scott (La Chute du faucon noir, 2002) ou Paul Haggis (Collision, 2005).
Au cinéma, le comédien reste cantonné à des seconds rôles qui, toutefois, marquent souvent l'imaginaire des spectateurs. C'est grâce à la télévision qu'il gagne une popularité internationale, notamment avec la série Prison Break, qu'il rejoint en 2006 dans le rôle de l'inspecteur Mahone. Avant cela, il s'était illustré dans la série de science-fiction Invasion, et après l'arrêt de Prison Break en 2009, on peut le voir dans quelques épisodes de la série comique Entourage.
William Fichtner prête aussi régulièrement sa voix pour des jeux vidéo, et le fait notamment pour deux épisodes de Grand Theft Auto ainsi que pour Call of Duty: Modern Warfare 3. En 2005, il s'essaye à un genre qu'il a peu pratiqué, la comédie, avec Mi-temps au mitard. Il récidive deux ans plus tard, se retrouvant à l'affiche des Rois du patin, ainsi qu'en 2010 avec Crazy Night.
L'acteur continue également à tourner dans des films à gros budget comme The Dark Knight (2008), où il fait face au Joker Heath Ledger dans un prologue détonant, ou encore The Lone Ranger (2013) aux côtés de Johnny Depp, et Elysium (id.) avec Matt Damon. Cependant, il se voit aussi confier un rôle d'importance dans le plus modeste et étrange Wrong du Français Quentin Dupieux.