Choi Min-sik s'est d'abord fait connaître par le théâtre avant de percer dans l'industrie cinématographique dans le film Our Twisted Hero en 1992 de Park Chong-won, qui rencontre un bon succès au près des critiques de cinéma et du public. Au milieu des années 1990, il continue de jouer des rôles au théâtre ainsi que dans de nombreuses séries télévisées, dont notamment Moon Over Seoul avec Han Seok-gyu. L'année 1997 marque son retour sur la scène cinéma avec un rôle de policier dans le film No. 3. Le rôle qui le révèle véritablement au cinéma sera son rôle de terroriste nord-coréen dans le film Shiri. Ce n'est pas le rôle principal de ce film qu'on a appelé "le premier blockbuster coréen", mais son interprétation étonne notamment lors d'une scène où il crie la douleur de ses compatriotes nord-coréens. Le rôle lui vaudra deux prix d'interprétation.
Au printemps 1999, il joue Hamlet au théâtre avant de revenir au cinéma avec le film Happy End où il joue le rôle d'un mari apprenant l'infidélité de sa femme. En 2001, il interprète un gangster de bas étage à la recherche d'une femme qu'il a épousé sans même la connaître dans le film Failan, aux côtés de l'actrice hongkongaise Cecilia Cheung. Le film est salué par la critique.
En 2003, c'est la consécration avec le film Old Boy. Depuis, il a fait une apparition dans Frères de sang, jouant encore une fois le rôle d'un soldat nord-coréen ainsi que dans Crying Fist, où il interprète avec conviction un boxeur sur le déclin. Il tient également la tête d'affiche dans le film When Spring Comes où il interprète un chef d'orchestre dépêché dans un village de campagne pour enseigner la musique à des enfants. Choi Min-sik n'a pas peur des rôles difficiles et joue le rôle de l'horrible meurtrier d'enfants dans le film qui clos la trilogie de la vengeance de Park Chan-wook, Lady Vengeance, ou encore un serial-killer psychopathe dans le film de Kim Jee-woon, J'ai rencontré le Diable.
En 2006, emboîtant le pas à Jang Dong-gun, Choi Min-sik renvoie au gouvernement l'Ordre du Mérite Culturel qu'il a reçu pour son rôle dans Old Boy, afin de protester contre la réduction des quotas de diffusion des films nationaux : il refuse tous les scénarios qui lui parviennent et compte ne plus jouer dans aucun film si les quotas ne sont pas rétablis.
En 2014, outre un second rôle hors de Corée dans Lucy, il joue le rôle principal dans The Admiral: Roaring Currents, un film sur le héros coréen Yi Sun-sin qui devient le film le plus vu dans l'histoire en Corée du Sud.