Mark Addy grandit à Tang Hall dans le comté de York, au nord de l'Angleterre. Il débute dans la vie active à l'âge de quinze ans comme machiniste au York Theatre Royal puis il est formé au métier de comédien à la Royal Academy of Dramatic Art à Londres et fait ses preuves au Hull Truck Theatre Company et au Royal National Theatre. Durant les années 1990, alors qu'il arpente les planches, il fait ses premiers pas à la télévision des séries (Mr. Fowler, Brigadier chef...) et téléfilms Respect,The Heart Surgeon...).
En 1997, il apparaît pour la première fois sur grand écran et s'est tout de suite la consécration. En effet, son interprétation d'apprenti-strip teaseur dans la comédie à succès Full monty lui vaut des critiques élogieuses. Embarqué aux Etats-Unis, il donne la réplique à Michael Keaton dans Jack Frost (1998) avant de retrouver un rôle de tout premier rang dans Les Pierrafeu à Rock Vegas (2000). Continuant à s'illustrer dans la comédie familiale, il a pour partenaire Chris Rock dans Les Pieds sur terre (2001).
Brian Helgeland lui permet de varier son jeu d'acteur en le dirigeant à deux reprises aux côtés de Heath Ledger dans le film historique Chevalier (2001) et dans le thriller religieux Le Purificateur (2003). Il tourne ensuite dans le film de science fiction La Machine à explorer le temps - Time machine. Devant l'échec de ce dernier, l'acteur britannique retourne à la télévision et devient la star de la série familiale Une famille presque parfaite. Dans le même temps, il prête ses traits à un capitaine de steamer dans Le Tour du monde en 80 jours de Frank Coraci. Après l'arrêt d'Une famille presque parfaite, Mark Addy retourne en Angleterre pour tourner dans la mini-série The Red Riding Trilogy, aux côtés des jeunes Andrew Garfield et Rebecca Hall.
En 2010, Mark Addy revient sur le devant de la scène en apparaissant au générique du Robin des Bois de Ridley Scott, où il campe un moine, ami du célèbre voleur au grand cœur. Un an plus tard, on le retrouve dans la comédie Le Monde de Barney en compagnie de Dustin Hoffman et Paul Giamatti, ainsi que dans la série à succès Le Trône de fer, adaptation du livre éponyme.