D'origine britannique et costa-ricaine, Madeleine Stowe débute une carrière de comédienne dans un théâtre de Beverly Hills. Elle est ensuite à l'affiche de plusieurs productions télévisuelles, dont The Gangster chronicles : an american story (1981), durant laquelle elle rencontre son futur mari, l'acteur Brian Benben. En 1987, elle est la jeune femme placée sous la surveillance de Richard Dreyfuss dans la comédie policière Etroite surveillance de John Badham.

Son charme et son romantisme sont mis en valeur dans Two jakes (la suite de Chinatown, 1990) et le thriller Revenge de Tony Scott avec Kevin Costner (id.). Elle interprète ensuite Cora Munro, la jeune femme éprise du Dernier des Mohicans (1992). Continuant sur sa lancée, elle joue dans le Short cuts (1993) de Robert Altman, film chorale dans lequel elle est une femme trompée s'accrochant désespérément à son mari. Suivent le western au féminin Les Belles de l'Ouest et deux autres thrillers : Blink, où elle est témoin d'un meurtre, et Lune rouge, où elle fait figure de femme fatale face à Ed Harris.

Les plus grandes stars masculines se l'arrachent à l'écran : Bruce Willis dans le futuriste L'Armée des 12 singes (1996), John Travolta dans le thriller militaire Le Déshonneur d'Elisabeth Campbell (1999), Mel Gibson dans le film de guerre Nous étions soldats (2002) et Sylvester Stallone dans la comédie mafieuse Mafia love (id.).