A la sortie du collège, Martin Landau étudie les beaux-arts à l'Institut Pratt et devient illustrateur pendant cinq ans au quotidien "New York Daily News". Passionné de théâtre, il se présente en 1955 pour une audition à l'Actor's Studio, où il est retenu en compagnie de Steve McQueen. Dans la célèbre école, ses professeurs prestigieux se nomment Lee Strasberg, Elia Kazan, Harold Clurman et Curt Conway, notamment.

Il monte sur les planches de Broadway dans Goat Song, Stalag 17, Detective Story. Mais c'est surtout avec la tournée de Middle of the night, son premier grand succès d'acteur, que Martin Landau se fait remarquer par les grands metteurs en scène hollywoodiens. Il attire l'attention dès sa seconde apparition au cinéma en incarnant Leonard, l'âme damnée de l'espion Philip Van Damme (James Mason) dans La Mort aux trousses d'Alfred Hitchcock en 1959.

Au milieu des années soixante, il devient célèbre pour des millions de téléspectateurs en prêtant ses traits à Rollin Hand, le personnage à transformations de la série culte Mission : Impossible, aux côtés de sa femme Barbara Bain, épousée en 1957. Il fera partie des trois premières saisons diffusées entre 1966 et 1969, avant d'être remplacé par Leonard Nimoy. Conséquence de son activité régulière à la télévision, sa carrière cinématographique se poursuit à un rythme ralenti. En 1975, il s'installe avec son épouse en Angleterre où ils seront tous les deux les vedettes d'un nouveau feuilleton télévisé, Cosmos 1999, de 1975 à 1977. Ses rôles s'orientent désormais vers la science-fiction, notamment avec Meteor en 1979 et Terreur extraterrestre en 1980.

Après son divorce en 1987, sa carrière au cinéma prend un nouvel essor avec deux nominations consécutives à l'Oscar du Meilleur Second Rôle masculin pour Tucker en 1988 et pour Crimes et Delits en 1989. Il obtient finalement l'Oscar et la consécration en incarnant l'acteur Bela Lugosi dans le désormais classique Ed Wood de Tim Burton, en 1994.

Depuis, Martin Landau ne cesse de travailler pour le cinéma. Il prête entre autres ses traits à Geppetto, le fabricant de marionnettes de Pinocchio en 1996, rôle qu'il reprend en 1999 dans Pinocchio et Gepetto. La même année, il retrouve Tim Burton dans Sleepy Hollow, la légende du cavalier sans tête pour jouer Peter Van Garret : un petit rôle certes, mais déterminant dans l’histoire puisqu’il est la première victime du cavalier sans tête joué par Christopher Walken. Tout en continuant de tourner pour la télévision et dans des séries telles que The Evidence : les preuves du crime ou FBI : portés disparus, l’acteur enchaine les tournages, aussi bien pour des comédies comme Ready to Rumble en 2000, que pour des drames comme The Majestic en 2002, où son personnage croit reconnaitre en Jim Carrey son fils, parti à la guerre quelques années plus tôt.

En 2008, l'acteur fait partie des habitants d’une ville souterraine dans La Cité de l'ombre en compagnie de Bill Murray, avant d’incarner le mystérieux Harrison Montgomery. L'année suivante, il s'essaie à l'exercice du doublage et prête sa voix à l'une des petites marionnettes survivantes de Numéro 9. Ce long métrage d’animation, réalisé par Shane Acker, est produit par Tim Burton. En 2012, les deux hommes se retrouvent pour une quatrième collaboration avec Frankenweenie : le comédien y est à nouveau engagé en tant que doubleur, cette fois-ci pour donner vie à l'étrange M. Rzykruski.