L’idée de départ qui donna naissance à L’Armée des 12 singes a germé dans l’esprit du producteur exécutif Robert Kosberg, un grand admirateur du court métrage expérimental La Jetée du réalisateur français Chris Marker. Il a persuadé Universal d’en acheter les droits pour en faire un remake.
Un passage du film montre nos deux héros en fuite se réfugiant dans un cinéma où se joue Sueurs froides (Vertigo) d'Alfred Hitchcock. On y voit alors un extrait du film, où les personnages joués par James Stewart et Kim Novak se trouvent dans le parc Big Basin Redwoods State de Santa Cruz, en Californie. Ils évoquent le passage du temps devant la coupe d'un séquoia, l'actrice montrant " Ici je suis née… et ici, je suis morte ". L'extrait du film d'Hitchcock fait ainsi directement écho au voyage dans le temps et au destin du personnage de James Cole, incarné par Bruce Willis.
Le titre du film de Terry Gilliam, L'armée des douze singes est inspiré du roman de Frank Baulm : Le magicien d'Oz dans lequel le roi convainc douze singes de devenir ses soldats.
L'armée des douze singes de Terry Gilliam a remporté le Saturn Award du meilleur film de science-fiction de 1995. Le film a aussi été en compétition en pour l'oscar du meilleur acteur dans un second rôle pour Brad Pitt, qui gagna tout de même un Golden Globe pour sa prestation, ainsi que pour l'oscar des meilleurs costumes. A la liste des nominations vient s'ajouter celle pour l'ours d'or du festival de Berlin, en 1996.
Terry Gilliam donna à Bruce Willis une liste des "Willis acting clichés", c'est-à-dire des "Clichés du jeu de Willis", à ne surtout pas utiliser durant le film. Parmi eux "les yeux bleus au regard d'acier".
La voix du journaliste à la radio déclare : "This is Roger Pratt reporting", soit "Ici Roger Pratt qui parle". Roger Pratt est en réalité le directeur de la photographie du film.
Pour garder le contrôle du film et ne pas être à la merci des stars, Terry Gilliam souhaitait enrôler des acteurs peu connus. Les émissaires du studio protestèrent et ont passé des jours entiers pour le convaincre qu’une star ou deux pourraient assurer la promotion du film et son succès dans les salles. Gilliam mentionna Nick Nolte dans le rôle de James Cole et Jeff Bridges dans le rôle de Jeffrey Goines. Au final Universal lui proposa Bruce Willis et après un après-midi passé avec lui, Gilliam donna son accord.
Terry Gilliam souhaitait garder l’esprit d’une petite production, pour ce faire il demanda à ses deux acteurs vedettes Bruce Willis et Brad Pitt de renégocier leur cachet à la baisse : Willis fut payé en pourcentage sur les recettes et Brad Pitt toucha un demi-million de dollars soit trois fois moins de ce qu’il pouvait prétendre à l’époque.
Terry Gilliam a choisi les paysages post-industriels délabrés de Philadelphie et de Baltimore comme lieu de tournage. Un ancien pénitencier fut sélectionné pour tourner les scènes de l’hôpital psychiatrique car le réalisateur trouvait que les hôpitaux modernes ressemblaient à des bureaux. "Cela me fascinait par avance de tourner à Philadelphie parce qu’il se dégage de son architecture un incroyable parfum de décadence et de pourriture. Or j’ai tout de suite ressenti L’Armée des douze singes comme un film sur l’échec, la décomposition, la nostalgie"
Terry Gilliam craignait que Brad Pitt n’aurai pas un phrasé assez nerveux et rapide pour incarner son personnage, il lui demanda donc de suivre un entraînement auprès d’un coach. Au final Gilliam demanda à Pitt de ne plus fumer et il put jouer son rôle exactement comme le réalisateur l’avait imaginé.
Dans la scène où James Cole se prélève du sang, on peut voir l’ombre d’un hamster en train de tourner dans sa roue projetée sur un mur. Cette scène devait à la base être tournée en cinq minutes mais comme le hamster ne voulait pas bouger, cela prit une journée entière à cause du perfectionnisme de Terry Gilliam. Pour le reste du tournage, cette péripétie fut appelée le "Hamster Factor"
L’artiste et architecte Lebbeus Woods a intenté un procès contre Universal Pictures en février 1996. Il affirme que son dessin Neomechanical Tower (Upper) Chamber, publié dans les années quatre-vingt, avait été utilisé sans autorisation dans une scène du film. La justice donna raison à Woods et somma Universal de retirer le film des salles. Universal obtenu de Woods de pouvoir diffuser le film sans coupures après lui avoir donné une compensation financière de plusieurs centaines de milliers de dollars.
Pour la première fois de sa carrière Terry Gilliam a eu le privilège d’avoir le final cut, une fois le tournage fini. Une réelle surprise pour lui, après les fameuses disputes auprès d’Universal notamment avec son dirigeant de l’époque Sidney Sheinberg qui souhaitait changer radicalement la structure du film Brazil.
Terry Gilliam a choisi d’enrôler Madeleine Stowe pour jouer le personnage du Dr. Kathryn Railly car il avait été impressionné par sa performance dans Blink. Le réalisateur a rencontré Stowe quand il passait un casting pour son adaptation filmique du célèbre roman de Charles Dickens : Le Conte de deux cités. "Elle est d’une beauté délicate et elle est incroyablement intelligente" précisa Terry Gilliam, il ajouta aussi : "Elle peut user de ses deux qualité aisément et le film avait besoin de ses deux éléments car il se devait d’être romantique."
Terry Gilliam et le producteur Charles Roven ont eu plusieurs disputes quant à la fin du film. Gilliam a essayé de dissuader Roven en lui proposant une installation complexe nécessitant deux grues se chevauchant ainsi qu’un nombre conséquent de voitures. En effet, il espérait que Roven trouve la scène bien trop chère à filmer et qu’il finirait par l’annuler. Á sa grande surprise, le producteur donna son accord, par ailleurs Gilliam adora le résultat et dans la foulée décida de le garder pour la fin du long métrage.
Le Walters Art Museum qui se situe à Baltimore a été mis à profit pour tourner la scène où le docteur Railly est introduite. Le film s’ouvre sur un gros plan de la toile The Ideal City une des pièces maîtresses de ce musée ainsi qu’une des toiles préférées de Terry Gilliam.