À 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.
L'Introduccion de la Suite Punta del Este d'Astor Piazzolla est utilisée comme un leitmotiv tout au long du film.
Au début du film, James est amené dans la salle d'interrogatoire où on le fait asseoir sur une chaise qui est attachée à un rail vertical sur le mur. Une sphère soutenue par une armature métallique fait face de Joe, pour sonder les points faibles pendant que les inquisiteurs l'interrogent. L'architecte Lebbeus Woods a intenté un procès contre Universal Pictures en février 1996, affirmant que son dessin « Neomechanical Tower (Upper) Chamber », publié en 1987, avait été utilisé sans autorisation.
La justice a donné raison à Lebbeus Woods, a ordonné à Universal Pictures de retirer le film des salles et en a interdit la diffusion tant que les trois scènes où apparait ce décor ne seraient pas coupées. Moyennant un accord en millions de dollars, Universal Pictures a obtenu de Woods de pouvoir diffuser le film sans coupures.