Né d'un père serbe et d'une mère tchèque, Karl Malden travaille d'abord dans une usine d'acier avant de se consacrer au théâtre en partant s'installer à New York. Il commence à jouer dès 1937 au sein du fameux Group Theater, où il va attirer l'attention du metteur en scène Elia Kazan, avec qui il entamera une collaboration fructueuse.
Son interprétation de Mitch dans Un tramway nommé désir lui offre l'Oscar du Meilleur Acteur en 1951. Il apparaîtra dans deux autres films très célèbres de Kazan, Sur les quais, dans le rôle du père Barry, et La Poupée de chair, où il interprète l'aristocrate décadent Archie Lee Meighan. Son physique massif devient familier du grand public, tout autant que ses personnages de brutes autoritaires ou de militaires jusqu'au-boutiste.
Dans les années 50, Karl Malden travaille avec les plus prestigieux metteurs en scène américains, comme Otto Preminger (Mark Dixon détective), Alfred Hitchcock (La Loi du silence) ou Richard Brooks (Sergent la terreur). En 1961, il est le shérif Dad Longworth de La Vengeance aux deux visages pour son collègue Marlon Brando. Karl Malden travaille aussi à deux reprises avec plusieurs réalisateurs : Delmer Daves sur La Colline des potences et La Soif de la jeunesse, John Frankenheimer pour L' Ange de la violence et Le Prisonnier d'Alcatraz, et John Ford sur deux westerns, La Conquête de l'ouest et Les Cheyennes.
Il joue ensuite aux côtés de Michael Caine dans Un cerveau d'un milliard de dollars, l'un des premiers films de Ken Russell, puis épaule George C. Scott dans Patton. Au cours des années 70, le cinéma de genre italien le réclame (Le Chat à neuf queues), puis c'est le tour du petit écran : à partir de 1972, il joue régulièrement dans la série télévisée Les Rues de San Francisco, avec une jeune star prometteuse, Michael Douglas.
On le voit aussi dans des publicités vantant les mérites de la carte American Express. En 1988, il préside l'Academy of Motion Picture Arts and Sciences pour cinq années. Malden publie ses mémoires, intitulées When do I start ?. Il poursuit essentiellement sa carrière d'acteur à la télévision, dans des séries et des téléfilms.