Когда в гитлеровской Германии официально объявили о создании люфтваффе, Мельдерс уже учился в школе бомбардировщиков, а затем он закончил и школу истребителей в Шлиссхайме. К тому времени его летное мастерство уже не вызывало сомнений, и особенно восхищала инструкторов меткость его стрельбы. Военную службу Мельдерс начал в штурмовой авиагруппе «Шверин» (впоследствии преобразованной в 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. Кроме меткой стрельбы, Мельдерс отличался также великолепным зрением, и он приложил немало усилий, чтобы еще больше развить этот ценный для летчика-истребителя дар.