В юности Вальтер активно занимался спортом, особенно легкой атлетикой. Он занял третье место в метании копья и первое в беге на 1000 метров на чемпионате Нижней Австрии. Летом 1936 г. он в качестве зрителя посетил Олимпийские игры в Берлине.
В мае 1938 г. Новотны успешно сдал выпускные экзамены в гимназии, после чего отработал шестимесячную трудовую повинность в «Имперской службе труда», которая была обязательной для всех трудоспособных граждан Третьего рейха от 19 до 25 лет.
1 октября 1939 г. Новотны добровольцем вступил в Люфтваффе и был направлен во 2-й батальон 62-го учебного полка, расквартированный в г. Кведлинбург, в 50 км юго-западнее Магдебурга, для про хождения первоначальной военной подготовки.
16 ноября его направили в только что созданную истребительную авиашколу «Вена-Швехат», находившуюся, как следовало из ее на звания, на аэродроме Швехат, в нескольких километрах от юго-восточной окраины Вены. Там Новотны познакомился с Карлом Шноррером, который стал его другом, а позднее и ведомым. Вместе с ними в Швехате летную подготовку проходил и Пауль Галланд – младший брат уже получившего известность Адольфа Галланда.
1 июля 1940 г. Новотны присвоили звание фенриха. В августе он впервые поднялся в воздух на истребителе Bf109. Как и большинство молодых пилотов, Новотны не сразу освоил «Мессершмитт», который из-за узкой колеи шасси требовал от пилота особого внимания при взлете и посадке. В итоге один из его вылетов завершился посадкой «на брюхе».
16 ноября Новотны вместе с двумя своими товарищами прибыл в учебно-боевую истребительную группу «Мерзебург» под командованием майора Альберта Блюмензаата. Она располагалась на одно именном аэродроме, в 27 км западнее Лейпцига, и ее основной задачей было прикрытие нефтеперерабатывающих и химических заводов, находившихся около города Лойна, в нескольких кило метрах к югу. Однако уже 19 ноября группу «Мерзебург» распустили, а весь ее персонал распределили по различным истребительным эскадрам Люфтваффе.
Новотны же 1 декабря назначили во вновь сформированную Ergenzungsstaffel JG54 во главе с обер-лейтенантом Цилкеном. Это была учебно-боевая эскадрилья, занимавшаяся вводом в строй молодых летчиков. Тогда она размещалась на юге Франции, на аэродроме Казо, недалеко от побережья Бискайского залива.
Выпускники 5-й истребительной авиашколы, осень 1940 г. Слева направо: фенрих Новотны, фенрих Пауль Галланд, фенрих Ульрих Буркхардт.
В феврале 1941 г. эскадрилью преобразовали в Erg.Gr. JG54. В новой группе имелись две эскадрильи: боевая – 1.Einsatzstaffel, и учебная – 2.Ausbildungsstaffel. Новотны вошел в состав первой эскад рильи. 23 февраля его отправили на дополнительную стажировку в 9./JG54, которая также базировалась во Франции на аэродроме Ле Ман. Спустя месяц – 25 марта – он вернулся в Erg.Gr.JG54, которой к этому времени уже командовал обер-лейтенант Эггерс. Новотны был включен в состав штабного звена и 1 апреля получил звание лейтенанта.
В мае 1941 г. Erg.Gr. JG54 перебросили в Восточную Пруссию. Группа разместилась на аэродроме Нойкурен, в 32 км северо-запад нее Кенигсберга (ныне соответственно Пионерский и Калинин град), поблизости от побережья Балтийского моря.
Начиная с 22 июня штабное звено группы и 1.Einsatzstaffel принимали участие в начавшихся боевых действиях на Восточном фронте. Благодаря своему энергичному и бесстрашному поведению в бою Новотны выделялся среди других пилотов. Однако в то же время он был очень импульсивным и склонным к индивидуализму, и именно эти черты вскоре чуть было не стоили ему жизни.
Части Вермахта быстро продвигались вперед, и уже в июле Erg.Gr. JG54 перелетела дальше на северо-восток, на аэродром Виндау (ныне Вентспилс, Латвия). Вечером 19 июля Новотны вместе с ведомым вылетел на «свободную охоту» к острову Озель (ныне Саа ремаа) в Рижском заливе. Это был уже его 34-й боевой вылет. Чтобы спровоцировать советские истребители подняться в воздух, «Меcсершмитты» начали описывать круги над советским аэродромом в Аренсбурге (ныне Курессааре). Новотны не ошибся, и вскоре в воздух поднялись четыре И153 из 153го ИАП во главе с командиром эскадрильи старшим лейтенантом Александром Авдеевым.
Новотны быстро добился первого успеха, сбив в течение двух минут две «Чайки». В какой-то момент он заметил позади себя самолет. Мельком взглянув назад, пилот успел отметить лишь белый кок винта. Он подумал, что это ведомый, но в действительности это был истребитель Авдеева. На некоторых И153 из 153-го ИАП коки винтов были окрашены в белый цвет, точно так же как и на истребителях JG54.
Позднее Новотны написал: