Après des études de contrepoint et de composition avec Eusebius Mandyczewski, Guido Adler et Franz Schmidt, il dirige quelques représentations d'opéra à l'Urania de Vienne. C'est en autodidacte qu'il se tourne alors vers une carrière de chanteur, faisant ses débuts en 1926 à Liberec dans Radames (Aida). Après une saison à Brno, il est engagé à l'Opéra d'État de Bavière à Munich, où il est premier ténor jusqu'en 1945. Après la Seconde Guerre mondiale, il quitte Munich pour l'Opéra national de Vienne, dont il restera membre jusqu'en 1960. Il continuera néanmoins de chanter jusqu'en 1967.
Patzak est particulièrement apprécié dans les opéras de Mozart, et plus généralement dans tous les rôles d'anti-héros tels que Florestan (Fidelio de Beethoven), Palestrina (dans l'opéra homonyme de Pfitzner), Mime (L'Or du Rhin et Siegfried de Wagner), Hérode (Salome de Richard Strauss) ou encore Eisenstein (La Chauve-souris de Johann Strauss), auxquels le timbre très particulier de sa voix le prédestinait. Sa très solide formation musicale en a fait un chanteur de concert très apprécié des plus grands chefs, particulièrement pour les passions de Bach. Son interprétation du Chant de la terre de Malher, aux côtés de Kathleen Ferrier et sous la direction de Bruno Walter, le chef qui avait assuré la création de l'œuvre en 1911, fait figure de référence. Sa contribution, amplement attestée par le disque, à l'art du Lied est une des plus importantes de son époque. Avec Elfriede Ott, il a également chanté des lieder de la tradition du théâtre populaire viennois.
Par ailleurs il a enseigné le chant à l'Académie de musique de Vienne et au Mozarteum de Salzbourg. Il était marié avec Maria Walter, fille du ténor Raoul Walter, fils du ténor Gustav Walter.