Когда в гитлеровской Германии официально объявили о создании люфтваффе, Мельдерс уже учился в школе бомбардировщиков, а затем он закончил и школу истребителей в Шлиссхайме. К тому времени его летное мастерство уже не вызывало сомнений, и особенно восхищала инструкторов меткость его стрельбы. Военную службу Мельдерс начал в штурмовой авиагруппе «Шверин» (впоследствии преобразованной в StG 2 «Иммельман»), где он пробыл, впрочем, недолго и в апреле 1936 года был переведен в истребительную эскадру JG 134. Через год дослужился до командира эскадрильи.

Гражданская война в Испании превратилась в настоящий полигон для немецких летчиков, стремившихся набраться боевого опыта. Не стал исключением в этом вопросе и Мельдерс, неоднократно писавший рапорты с просьбой направить его на фронт. Однако его желание удовлетворили лишь в апреле 1938 года, когда в авиагруппе J 88 «Легиона Кондор» появилось вакантное место заместителя командира эскадрильи. На вооружении двух эскадрилий J 88 в тот период состояли истребители-монопланы Bf 109В, а еще две эскадрильи летали на бипланах Не 51, применявшихся в основном для штурмовки наземных целей. Мельдерса направили в подразделение, оснащенное устаревшими Не 51. В мае 1938 года он возглавил это подразделение, сменив убывшего в Германию ее прежнего командира Адольфа Галланда. За месяц до этого события эскадрилья перевооружилась на Bf 109С.

Свою первую воздушную победу Мельдерс одержал 15 июля 1938 года. Его жертвой стал республиканский истребитель И-15. Через день он записал на свой счет еще один сбитый И-15, а 19 июля пополнил список побед истребителем И-16. Всего в течение испанской «командировки» Мельдерс, по немецким данным, сбил 14 республиканских самолетов, среди которых были 2 И-15, 11 И-16 и 1 бомбардировщик СБ. Таким образом, он стал самым результативным летчиком-истребителем немецкого «Легиона Кондор». Однако гораздо важнее для люфтваффе оказались заслуги Мельдерса в области разработки тактики действий истребительной авиации. Так, он был противником маневренных боев с вражескими истребителями и всегда советовал атаковать противника с выгодной позиции, используя фактор внезапности, а затем уходить на максимальной скорости, чтобы занять новое положение для атаки. Учитывая скоростные и аэродинамические характеристики Bf 109, такая манера боя в Испании являлась для этого самолета оптимальной. Следует заметить, что этот опыт он перенял у пилотов республиканских истребителей И-16, которые предпочитали вести бои в вертикальной плоскости, в то время как более маневренные И-15 сражались по горизонтали. В качестве основной боевой единицы истребителей Мельдерс ввел в обращение пару самолетов, выгодно отличавшуюся от популярного в то время звена из трех машин. Треугольное боевое построение истребителей, красивое на параде, было совершенно неэффективным в зоне боевых действий, поскольку ведомым больше приходилось следить за соблюдением дистанций в строю, чем за окружающим пространством. После начала боя тройка обычно распадалась на отдельные самолеты. В свою очередь, пара истребителей давала пилотам значительно большую свободу маневра. В сражении истребители быстро перестраивались, сохраняя за счет этого свой боевой порядок и прикрывая друг друга от вражеских атак. Две пары немецких истребителей составляли звено, которое в воздухе образовывало строй, получивший название «четыре пальца». Первая пара летела впереди, а вторая пара несколько сдвигалась назад, и на виде сверху самолеты занимали позиции как бы на кончиках пальцев руки.

Возвратившись в Германию уже известным пилотом, Мельдерс несколько месяцев работал в министерстве авиации Германии, где получил возможность внедрить в наставления люфтваффе все свои идеи по тактике. В марте 1939 года он был назначен командиром эскадрильи 3./JG 53.

К началу Второй мировой войны 53-я эскадра базировалась в западной части Рейха и в нападении на Польшу не участвовала. Однако объявленная англо-французским командованием «странная война» вскоре привела к воздушным стычкам и на западной границе страны. Свой первый после Испании бой Мельдерс провел уже 8 сентября 1939 года, когда звено Bf 109Е из JG 53 встретилось в воздухе с пятью французскими истребителями Кертисс Н.75. Единственным сбитым в этом поединке оказался сам Мельдерс, который в процессе вынужденной посадки скапотировал и лишь по чистой случайности остался невредим. Взять реванш ему удалось 20 сентября, уничтожив Н.75 из группы II/5. Через месяц он сбил английский бомбардировщик «бленхейм», а 22 декабря отправил к земле «харрикейн». К этому времени он уже командовал группой III/JG 53. Кроме меткой стрельбы, Мельдерс отличался также великолепным зрением, и он приложил немало усилий, чтобы еще больше развить этот ценный для летчика-истребителя дар.

К моменту вторжения немецких войск во Францию Мельдерс имел на счету 24 воздушные победы, и еще 15 самолетов он сбил в ходе сражений над французской территорией. Его 128-й боевой вылет едва не оказался последним. Мельдерс так описывал события 6 июня 1940 года: «Сверху появились три неопознанных самолета. Набрав высоту 7000 м, мы увидели наши «мессершмитты». Вновь снизились и развернулись домой. Внезапно объявились шесть «моранов» — преследую их сзади. По мере сближения разглядел еще две эскадрильи «мессершмиттов», уже вступивших в бой с противником. Они первыми начали поединок, и я ушел в сторону, чтобы осмотреться. Завязался обычный бой. «Мораны» дрались отчаянно — один «мессершмитт» в пламени врезался в землю; пилот, наверное, погиб. Некоторое время я наблюдал за схваткой, а затем атаковал «моран», который безрезультатно обстреливали три «мессершмитта». Вскоре мне удалось поймать вражеский самолет в прицел, но он постоянно маневрировал, а затем внезапно выполнил переворот и оказался сзади и несколько ниже меня. Черт побери — француз открыл огонь.

Я заложил вираж и ушел в сторону солнца. Противник, по-видимому, потерял меня, так как развернулся в противоположную сторону и скрылся из виду. Надо мной пара «мессершмиттов» продолжала преследование последнего «морана». Он пытался уйти вниз, увертываясь из пулеметных очередей. Я посмотрел назад. Высота была примерно 800 м. Вдруг раздался грохот, и искры рассыпались по кабине моего самолета. Рычаг управления двигателем разлетелся на кусочки, а ручка управления провалилась вперед. Я начал падать вертикально вниз, и оставалось только покинуть самолет…».

Победителем Мельдерса стал су-лейтенант Помье-Лераг, пилот не «морана», а Девуатина D.520 из GC И/7. Зажатый затем в «клещи» тремя Bf 109, молодой французский летчик погиб, так и не узнав знаменитой фамилии сбитого врага! Мельдерс благополучно спустился на парашюте, но попал в плен и следующие три недели питался в основном лагерной похлебкой. Освободили его 30 июня после капитуляции Франции — на родине немецкого аса ожидали торжественная встреча и очередной чин майора.

Новый военный тур Мельдерс начал в июле 1940 года в должности командира JG 51, но в первом же вылете к берегам Британии ему опять не повезло. В районе Дувра он сбил истребитель «спитфайр», но затем был ранен в воздушном бою и едва дотянул на изрешеченном Bf 109 до своего аэродрома, рядом с которым приземлился, не выпуская шасси. Вновь к своим обязанностям после выздоровления Мельдерс приступил в августе 1940 года.

С этого времени он стал быстро наращивать список воздушных побед. 20 сентября на его счету имелось уже 40 сбитых самолетов (+14 — в Испании), а 22 октября — 50.