Diplômée de musique à l'université de Santa Cruz, en Californie, Rebecca Romijn est découverte par un agent à Paris, où elle s'installe pendant deux ans. Elle devient mannequin et fait, dès 1992, la couverture des magazines Elle, Cosmopolitan, People, Marie-Claire, Glamour, FMH, Shape, GQ, Sports Illustrated. Elle s'illustre également dans de nombreux spots publicitaires pour les marques Tommy Hilfinger, Pantene, Christian Dior, Victoria's Secret ou encore Miller Lite. Entre 1997 et 1999, son physique de rêve lui vaut d'être sélectionnée parmi les "50 plus belles personnes du monde" par People et d'être nommée "Femme de l'Année" par GQ.
En 1997, Rebecca Romijn fait ses débuts d'actrice dans un épisode de la série télévisée Friends, puis apparaît en guest star dans le feuilleton La Fête à la maison où joue également John Stamos, qu'elle épouse en 1998. Au cinéma, elle figure aux génériques des comédies Dirty work (1998) de Bob Saget, Austin Powers - l'espion qui m'a tirée (1999) de Jay Roach et The Intern (2000) de Michael Lange.
En 2000, elle décroche un rôle de plus grande importance grâce à X-men de Bryan Singer. Dans cette adaptation cinématographique du célèbre comic book, elle interprète Mystique, une captivante et maléfique "métamorphe", capable de se transformer en toute personne ou objet de son choix. Rebecca Romijn tourne également sous la direction de grands réalisateurs : John McTiernan pour les besoins de Rollerball (2002), le remake du film de science-fiction de Norman Jewison, et Brian De Palma qui lui confie le rôle principal du thriller Femme fatale (id.), celui de Laure Ash, une jeune femme ténébreuse et vénale aux multiples identités.
Enfin, après avoir donné la réplique à Robert De Niro dans le thriller fantastique Godsend, expérience interdite, elle replonge dans l'Univers des Marvel comics avec The Punisher de Jonathan Hensleigh, puis avec X-Men 2 en 2002 et X-Men l'affrontement final en 2006 où elle retrouve son personnage de Mystique.