Casting
À l'origine, Terry Gilliam voulait Nick Nolte pour le rôle de James Cole et Jeff Bridges pour celui de Jeffrey Goines, mais Universal s'y opposa. Gilliam, qui avait rencontré Bruce Willis pour le casting du rôle tenu par Jeff Bridges dans le Roi Pêcheur, voyait l'interprétation de Cole par Willis évoquant « quelqu'un de fort et dangereux, mais aussi vulnérable » (« somebody who is strong and dangerous but also vulnerable »). Willis devait se faire faire trois tatouages chaque jour de tournage : un sur le crâne avec son numéro de prisonnier, et un code-barre de part et d'autre du cou.
Gilliam a porté son choix sur Madeleine Stowe car il avait été impressionné par sa performance dans Blink. Ils s'étaient rencontrés une première fois pour le casting de l'adaptation du Conte de deux cités de Dickens (projet finalement abandonné). Selon Gilliam, « elle a cette incroyable beauté éthérée, et elle est incroyablement intelligente ; ces deux choses viennent très facilement avec elle, et le film a besoin de ces éléments, car il doit être romantique. » (« She has this incredible ethereal beauty and she's incredibly intelligent. Those two things rest very easily with her, and the film needed those elements because it has to be romantic. »)
Pour le rôle de Jeffrey Goines, Gilliam n'était pas convaincu par Brad Pitt, mais s'est laissé convaincre par son directeur de casting. Le salaire de Pitt était relativement modeste, il était encore un acteur en devenir. Cependant, au moment de la sortie de l'Armée des douze singes, Entretien avec un vampire, Légendes d'automne et Se7en étaient sortis et avaient fait de Brad Pitt un acteur bankable, ce qui profita aux recettes du film. Quelques mois avant le tournage, Brad Pitt a passé quelques semaines dans le service psychiatrique de l'hôpital de Temple University pour préparer son rôle.
