Mark Strong est né en Angleterre d'un père italien et d'une mère autrichienne (il parle d'ailleurs couramment l'allemand, ainsi que quelques mots d'italien).
Après une année d'études pour devenir avocat à Munich, il décide de se tourner vers la comédie (comme un certain Gerard Butler, avec qui il jouera en 2008 dans RocknRolla), retourne à Londres, et s'inscrit au Royal Holloway, puis au Bristol Old Vic Theatre School.
A partir du début des années 90, il commence à apparaître à la télévision et au cinéma. L'un de ses premiers rôles notables au cinéma sera dans Carton jaune (1997), mais il faudra attendre la décennie suivante pour qu'il ne perce véritablement, en grande parte grâce à ses deux amis réalisateurs, Guy Ritchie et Matthew Vaughn. Pour le premier, il jouera dans Revolver, RocknRolla, et bien entendu Sherlock Holmes, et pour le second dans Stardust, le mystère de l'étoile et Kick-Ass.
Il apparaît aussi dans Tristan & Isolde, Syriana, Oliver Twist, Sunshine, Babylon A.D., Mensonges d'état, Robin des bois, Victoria : les jeunes années d'une reine, ou bien encore Green Lantern. Mark Strong, et ce malgré un caractère réputé pour être affable, deviendra le spécialiste des rôles de méchants au cinéma.
Mark Strong est aussi un acteur de théâtre renommé, qui fut en 2003 nommé aux Laurence Olivier Theatre Award pour sa performance dans la pièce Twelfth Night.
 
Le parrain de son plus jeune fils n'est autre que Daniel Craig.