1 февраля 1934 г. Мёльдерс получил звание обер-фенриха. Через месяц, 1 марта, его представили к званию лейтенанта и зачислили в отделение «Немецкой школы воздушных сообщений» в Котбусе, которым тогда руководил опытный военный летчик Альфред Келлер.

Там Мёльдерс совершал учебные полеты на самолетах Не-45 и W.34. На первоначальном этапе обучения его преследовали сильнейшие головные боли и головокружение, но снова его дух оказался сильнее физических слабостей. 31 декабря Мёльдерс успешно закончил обучение в Котбусе и уже 1 января 1935 г. прибыл в военную авиашколу «Шлайссхайм», располагавшуюся в нескольких километрах от северной окраины Мюнхена. Там его инструктором стал небезызвестный Адольф Галланд.

1 марта того же 35-го года в Германии официально объявили о создании военной авиации. 21 мая Мёльдерс, носивший до этого форму командира звена «Германского авиационного спортивного союза», официально получил знаки различия лейтенанта новых Люфтваффе. Затем 1 июля его включили во вновь формируемую авиагруппу «Шверин», которая стала первой штурмовой группой в составе Люфтваффе.

Одним из первых шагов Гитлера на пути к созданию Третьего рейха стало аннулирование т. н. Локарнских соглашений, основным из которых был Рейнский гарантийный акт. Последний гарантировал неприкосновенность германо-французской и германо-бельгийских границ и Рейнской демилитаризованной зоны, включавшей все немецкое левобережье Рейна и полосу шириной в 50 км вдоль правого берега реки.

И вот 7 марта 1936 г. германский рейхстаг с подачи фюрера аннулировал Локарнские соглашения. Вооруженные силы получили приказ войти в Рейнскую область. Мёльдерс принимал самое активное участие в этой операции. Пока наземные части двигались по дорогам, он вместе с пятью другими пилотами уже приземлился на аэродроме в Дюссельдорфе. Эта группа летчиков, восторженно встреченная местным населением, стала первым военным подразделением теперь уже в бывшей Рейнской демилитаризованной зоне.

1 апреля того же 36-го года Мёльдерсу присвоили звание обер-лейтенанта. Одновременно его перевели в истребительную авиацию и назначили командиром учебной эскадрильи в составе вновь сформированной II./JG134. Группа базировалась на аэродроме Верль, в 26 км северо-восточнее Дортмунда. Ее возглавлял майор Теодор Остеркамп – один из асов Первой мировой войны, имевший на счету 32 победы. Он пользовался огромным уважением у подчиненных, за глаза называвших его просто дядя Тео.

Лучшего командира нельзя было и желать. Именно у Остеркампа Мёльдерс научился рыцарскому отношению к воздушному бою. Да и он сам оказался хорошим командиром и инструктором. Под его началом в учебной эскадрилье делали летную карьеру будущие асы Люфтваффе – Гельмут Вик, Вальтер Оесау, Ханс Ханн и другие.

15 марта 1937 г. на аэродроме Эрбенхайм, в 10 км юго-восточнее Висбадена, была сформирована I./JG334, которую возглавил майор Хуберт Мерхарт фон Бернегг. Уже 13 апреля Мёльдерс был переведен в нее и возглавил 2./JG334.

Тем временем еще с осени прошлого года пилоты Люфтваффе в составе «Легиона „Кондор“ участвовали в гражданской войне в Испании на стороне сил генерала Франко. По истечении определенного времени они заменялись, чтобы как можно больше летчиков могли получить боевой опыт. Мёльдерса рекомендовал направить в Испанию еще его прежний командир майор Остеркамп, но прибыл туда он лишь 14 апреля 1938 г., да и то только благодаря трагическому стечению обстоятельств.

В марте 1938 г. заканчивался срок «зарубежной командировки» обер-лейтенанта Галланда, командовавшего 3.J/88 «Легиона „Кондор“. 22 марта в качестве плановой замены из Германии прибыл гауптман Хубертус Херинг, которому требовалось некоторое время, чтобы освоиться на новом месте и принять все дела. Однако спустя неделю – 30 марта – произошла трагедия. В ходе очередного вылета Не-51 гауптмана Херинга восточнее Сарагосы неожиданно столкнулся с самолетом лейтенанта Манфреда Михаэлиса. „Хейнкели“ рухнули на землю в районе городка Бухаралос, в 60 км юго-восточнее Сарагосы, и оба пилота погибли. Особую горечь этой потере придавало то обстоятельство, что произошло это отнюдь не в бою.

В итоге Галланду пришлось задержаться в Испании, ожидая, пока командование Люфтваффе подберет нового кандидата на замену. Выбор, и, забегая вперед, можно сказать, очень удачный, пал на Мёльдерса. Перед отъездом в Испанию тот в письме старшему брату Хансу писал: «Все, что нужно урегулировать, я сделал. Это необходимо на случай, если по каким-нибудь причинам я не смогу вновь вас увидеть. В то же время у меня совершенно странное внутреннее убеждение, что со мной ничего не случится. Мое имущество и вещи я распределил, по завещанию мама, Виктор и ты, каждый получит свою часть».

Поначалу Галланд, наученный предыдущими печальными событиями, довольно прохладно принял Мёльдерса. Однако уже вскоре, убедившись в его летных и командирских способностях, дал ему отличную аттестацию. И 24 мая 1938 г. Мёльдерс официально принял командование над 3.J/88, но еще в течение месяца находился под критическим наблюдением Галланда, прежде чем все окончательно убедились, что он пригоден для этой должности. Надо отметить, что именно в Испании за Мёльдерсом закрепилось прозвище Папочка, отражавшее его человеческие качества как командира и товарища.

Его эскадрилья была оснащена бипланами Не-51В и, несмотря на свой истребительный статус, до этого времени в основном выполняла задачи по непосредственной поддержке войск, нанося штурмовые удары по позициям республиканских войск. Однако в начале июня 3.J/88 начали перевооружать новыми Bf-109D. Несомненно, это событие стало поворотным моментом не только в жизни самого Мёльдерса, но можно с некоторым пафосом утверждать, что и в истории мировой военной авиации.

Пилотам потребовалось некоторое время, чтобы освоить новые истребители, и затем в июле они начали участвовать в боях. 15 июля «шестерка» во главе с Мёльдерсом в районе городка Альгар-да-Палансиа, в 15 км северо-западнее Сагунто, встретилась с группой из 45 республиканских самолетов. Первая атака Мёльдерса оказалась неудачной, это был его всего второй боевой вылет на «Мессершмитте». Разозленный на себя, он зашел на следующий И-15 и теперь не открывал огонь до тех пор, пока вражеский истребитель полностью не заполнил собой всю рамку прицела. От прямых попаданий в упор республиканский самолет взорвался в воздухе.

Эта первая воздушная победа показала Мёльдерсу, как он сам затем писал, что «несмотря на бешено колотящееся сердце и чувство пустоты в желудке, когда быстро сближаешься с противником, пилоту необходимо сохранять чистую и ясную голову». В том бою успеха добились еще два пилота 3.J/88 – лейтенанты Вальтер Оесау и Вольфганг Липперт, сбившие по одному самолету.

Тогда же Мёльдерс впервые столкнулся с большой проблемой уже чисто личного характера. Как и многие другие летчики, он, сбив первый самолет, затем после приземления испытал своеобразный моральный шок. Будучи прилежным и убежденным католиком, он тяжело переживал то, что его успех в бою был связан с возможной смертью человека, хоть и бывшего в тот момент его врагом. И надо сказать, что эта проблема осталась для Мёльдерса до самого конца в общем-то нерешенной.

В ходе последующих боевых вылетов он быстро пришел к выводу, что прежняя тактика действий истребителей, базировавшаяся на применении больших групп малоскоростных бипланов, безнадежно устарела. Летая плотными «тройками» на гораздо более скоростных «Мессершмиттах», пилоты большую часть времени должны были следить за тем, чтобы не столкнуться друг с другом, вместо того чтобы заниматься своим прямым делом в качестве истребителей, то есть искать и уничтожать самолеты противника.