Mytteis studeerde aan het conservatorium in Wenen en aan de Wiener Musikakademie. In de jaren 30 was hij lid van het radio-orkest van Charly Gaudriot. Tevens trad hij met een eigen kwintet op in Weense gelegenheden om jazz en swing te spelen. Vanaf 1943 trad hij in Café de l'Europe op met de Italiaanse zanger en gitaristVittorio Ducchini, pianistErnst Landl en de FransedrummerArthur Motta alsook, af en toe, musici als Hans Koller en Viktor Plasil. Er werden ook opnamen gemaakt, maar deze werden niet uitgebracht.[1] Na de nederlaag van het nationaalsocialisme speelde hij tevens in Hot Club Vienna. Met zijn solisten begeleidde hij op opnamen voor Telefunken, Minja Petja en Karl Hruschka. Hij componeerde nummers als Intermezzo in Swing, Guggi, Seit du gegangen en Am Himmel, da leucht' a Laternderl.