Мюллер закончил летную школу летом 1941 года и к боевым вылетам приступил в сентябре в составе эскадрильи 1./JG 77. Действуя с аэродрома Лоустари, он уже в течение месяца заявил о 8 сбитых самолетах, среди которых были 1 ДБ-ЗФ, 3 СБ, 2 И-16, 1 И-153 и 1 «харрикейн». К слову сказать, большинство из этих побед Мюллера не подтверждаются советскими документами.
Первый тур Мюллера на Восточном фронте длился недолго, так как в октябре 1941 года, с наступлением полярной ночи и общим затишьем в сражениях, эскадрилья 1./JG 77 была переброшена на аэродром Ставангер, расположенный в западной части Норвегии. Причина этого заключалась в том, что Гитлер все еще опасался вторжения союзников в Норвегию. Здесь немецкие летчики участвовали в боях лишь эпизодически, но тем не менее Мюллер все же умудрился сбить два английских патрульных самолета «Хадсон».
К новым сражениям в советском Заполярье немецкое командование начало готовиться уже в январе 1942 года, и специально для боевых действий на этом фронте была сформирована 5-я истребительная эскадра люфтваффе, получившая название «Айсмеер» (Полярное море). Вначале из числа эскадрилий 1./JG 77, 14. /JG 77 и 2./ZG 76 была образована группа I/JG 5, а затем на основе истребительных подразделений, размещенных ранее в Финляндии и Франции, создали группы II и III 5-й эскадры. После окончательного формирования эскадры весной 1942 года, бывшую эскадрилью 1./JG 77 включили в состав 2-й группы JG 5, и она получила соответствующее обозначение 6. /JG 5.
Эскадрилья 6. /JG 5, в которой служил Мюллер, возвратилась на аэродром Луостари в апреле 1942 года, как раз в разгар ожесточенных боев в Заполярье, развернувшихся и на земле, и в воздухе. Чтобы отнять у противника инициативу и лишить его возможности вести какие-либо крупные военные операции в весенне-летний период, части советской 14-й армии при поддержке подразделений и кораблей Северного флота предприняли наступление на вражеские позиции с одновременной высадкой на фланге морского десанта. Даже частичный успех этого наступления в дальнейшем мог гарантировать затишье на Карельском фронте и бесперебойные поставки в Мурманск и Архангельск военного снаряжения морскими конвоями союзников, количество которых в начале 1942 года значительно возросло.
Гитлер еще в марте 1942 года потребовал изолировать советское Заполярье от внешних связей и начать интенсивную борьбу с судоходством противника. Таким образом, центр борьбы переместился на море, где немецкий флот и люфтваффе пытались нарушить советские морские коммуникации. Одновременно фашистские самолеты приступили к массированным бомбардировкам порта и объектов Кировской железной дороги. Чтобы уменьшить подлетное время, немцы восстановили аэродромы на оккупированной советской территории, в частности аэродром Алакурти, где разместились пикирующие бомбардировщики Ju 87.
23 апреля 1942 года Рудольф Мюллер одержал очередные воздушные победы, записав в течение дня на свой счет сразу 5 сбитых самолетов (4 «харрикейна» и 1 СБ). Следует заметить, что немецкие летчики в этот период времени имели явное преимущество в воздухе, поскольку летали на усовершенствованных истребителях Bf 109F-4 с усиленным бронированием и более мощным 1200-сильным двигателем. Хотя в советских ВВС Заполярья были сформированы новые истребительные полки, они вооружались в основном устаревшими английскими истребителями «харрикейн», а также американскими «томахауками» и «китгихауками», которые тоже по летным характеристикам уступали немецким самолетам. Кроме того, летный состав этих полков включал преимущественно пилотов, наспех обученных в военное время и не имевших никакого боевого опыта.
26 апреля в списке Мюллера оказался двухмоторный истребитель Пе-3. В этот день 7 «петляковых» из 95-го ИАП совершили налет на аэродром Хебуктен, но уже на подходе к цели были атакованы двумя эскадрильями «мессершмиттов». Советским самолетам удалось прорваться к аэродрому и сбросить бомбы (на земле превратились в обломки 6 фашистских машин и еще 20 получили повреждения), однако за это пришлось заплатить немалую цену.
5 Пе-3 были сбиты, а остальные вернулись на базу с многочисленными пробоинами.
Через день Мюллер доложил о четырех сбитых «харрикейнах», а 29 апреля началось советское наступление, которое длилось до 13 мая 1942 года. Естественно, подразделения ВВС 14-й армии были привлечены для нанесения бомбовых и штурмовых ударов по немецким позициям, и это вызвало всплеск борьбы за воздушное господство. Уже в первый день наступления «мессершмитты» из 6./JG 5 сбили над линией фронта два биплана И-153, занимавшихся штурмовкой вражеских укреплений. Одного из них записал на свой счет Мюллер. Всего за последнюю неделю апреля он заявил 15 воздушных побед и еще о 13 сбитых советских самолетах (в основном «харрикейнах») Мюллер доложил в течение мая.