Опозоренный Марсель вернулся в рейх, но ненадолго. В январе 1941 года управление личного состава Люфтваффе назначило его в JG-27, направлявшуюся в Ливию для укрепления потрепанных в боях итальянских королевских ВВС (Regia Aeronautica).
Именно в Северной Африке и проявились в полной мере таланты Ганса Иоахима Марселя. Этому весьма способствовали следующие факторы: во-первых, на расположенных в пустыне базах Люфтваффе не было женщин, а во-вторых, наставником Марселя был командир его группы майор Эдмунд Нойман, мастер своего дела. Прошло совсем немного времени, и "Йохен" стал лучшим снайпером Люфтваффе. Иногда, одержав 6 побед, он возвращался на свой аэродром, истратив лишь половину боезапаса. Действительно, на то, чтобы сбить самолет противника, Марселю требовалось в среднем всего 15 пуль. В результате про личное дело забыли, а Марселю (на счету которого числилось 33 сбитых самолета) присвоили звание фаненюнкера. А в декабре 1941 года фельдмаршал Кессельринг вручил ему Германский Золотой крест.
Красивый и утонченный молодой офицер стараниями имперского Министерства пропаганды, использовавшего его образ для укрепления боевого духа немецкого народа, снискал огромную популярность. Письма от поклонников (в основном от поклонниц) он получал целыми мешками. Его прозвали Африканским Орлом, а итальянцы, которые просто боготворили Марселя, окрестили его Звездой Африки. Муссолини наградил летчика золотой медалью за храбрость. Такой медали не был удостоен даже сам Эрвин Роммель. Правда, в отличие от "Лиса пустыни", Марсель не говорил дуче что он о нем думает.
31 мая 1942 года фельдмаршал Роммель, преисполненный решимости как можно скорее завершить войну в пустыне, начал наступление. Обеспечивая поддержку наступления с воздуха, 3 июня Марсель атаковал над Газалой несколько "киттихоков" (Curtiss Kittyhawk) и сбил шесть из них за 11 минут. Три дня спустя он был награжден почетным знаком за 75 воздушных побед. Боевые действия в Северной Африке были такими ожесточенными, что уже 17 июня 1942 года Марсель сбил сотый самолет противника. В этот день он свалил на землю 10 вражеских машин, 6 из которых всего за 7 минут! Днем позже Марсель был произведен в гауптманы и отправлен в рейх, где Гитлер собственноручно наградил его Рыцарским крестом с Дубовыми Листьями Мечами. Естественно, что, находясь в отпуске, он постарался лично ответить на письма своих многочисленных поклонниц. Несмотря на великолепно проведенное время, Марсель не смог сбросить напряжение, вызванное непрерывными боями над бескрайней Ливийской пустыней, и выглядел усталым и опустошенным. 23 августа, когда продвижение Роммеля было остановлено в районе Эль-Аламейна, Марсель вернулся в свой JG-27. На североафриканском театре военных действий наступило временное затишье. Вскоре "Лис пустыни" сделал попытку выйти из тупика и начал сражение у хребта Алам-Хальфа. И снова Марсель со своей эскадрильей поддерживал наступление с воздуха. 1 сентября 1942 года он навсегда вошел в историю, уничтожив за 1 день 17 британских самолетов. Такого удара королевские ВВС еще никогда не получали (абсолютный рекорд установил майор Люфтваффе Эмиль Ланн, сбивший за один-единственный день 18 советских самолетов). На этот раз гауптман Марсель не праздновал победу. Ночью он лежал в своей постели с открытыми глазами и смотрел в потолок. Из-за возросшей активности британских ВВС в сентябре у него не было ни дня отдыха. Переутомление не сказывалось на его летных качествах. Вот что писал о Марселе Хайнц Иоахим Наварра: "Он заранее знает все намерения своего противника и наносит упреждающий удар. Когда он абсолютно уверен, что его огонь уничтожил врага, Марсель утрачивает к нему всякий интерес и атакует следующий самолет."