Летная карьера Руделя началась в июне 1938 года, когда после окончания авиашколы он получил назначение в штурмовую группу I/StG 168, дислоцированную около Граца в Австрии. Эта группа оснащалась пикирующими бомбардировщиками Ju 87. Изучение боевого самолета оказалось для Руделя непосильной задачей, и он также не представлял собой никакой ценности, как пилот. За полгода обучения его обошли по всем параметрам даже посредственные курсанты, и в конце концов инструкторы махнули на Руделя рукой. Как только подвернулся приказ вышестоящего штаба об отправке нескольких летчиков в училище разведывательной авиации, они туг же от него избавились, предварительно представив к званию лейтенанта.
После прибытия Руделя к новому месту службы неприятной неожиданностью для него стало, что из-за соответствующей характеристики его зачислили на отделение не пилотов, а штурманов-наблюдателей. Некоторым утешением было то, что штурманы-наблюдатели в самолетах-разведчиках люфтваффе выполняли обязанности командиров экипажей. Завершив курс обучения, Рудель попал в эскадрилью дальней разведки и в ее составе принял участие в военных действиях против Польши. Эта война осталась в памяти Руделя рутиной разведывательных полетов в условиях слабого противодействия зенитной артиллерии и отсутствия вражеских истребителей. Тем не менее за Польскую кампанию он получил свою первую награду — Железный крест 2-го класса. Однако в подразделении он не прижился, и уже в марте 1940 года его «отфутболили» в учебный полк, размещенный недалеко от Вены и предназначенный для ускоренной подготовки пилотов, призванных в люфтваффе из запаса. Штабная должность адъютанта в этом полку, естественно, не обещала Руделю быстрой карьеры, и он засыпал командование рапортами с просьбой о переводе его обратно в штурмовую авиацию. Его желание удовлетворили летом того же года, и он вновь отправился в свою прежнюю группу пикирующих бомбардировщиков, переименованную к этому времени в I/StG 76 и расположенную в Кане во Франции.
Второй этап освоения «штуки» (сокращенное название пикирующего бомбардировщика Ju 87) длился у Руделя еще полгода, и за этот период личный состав группы почти полностью сменился. Большинство из ее пилотов уже участвовали в боях на Западном фронте. Наконец, после дополнительной подготовки в Граце, Рудель в апреле 1941 года получил назначение в группу I/StG 2, действующую с аэродрома в Греции. К этому моменту он с горем пополам научился управлять самолетом и держаться в строю. Однако первым, кого Рудель на свою беду встретил в новом подразделении, оказался его бывший инструктор из Кана, который сразу же доложил командиру группы майору Хичхольду о том, что собой представляет его новый пилот. «Я знаю вас со слов адъютанта настолько хорошо, — заявил Хичхольд Руделю, — что вплоть до особых распоряжений я не позволю вам летать в моей группе». В результате вместо боевых вылетов Руделю пришлось заняться перегонкой поврежденных Ju 87 в Германию, где их ремонтировали в заводских условиях. Такая ситуация сохранялась до 22 июня 1941 года, когда немецкие войска вторглись на территорию Советского Союза и Германия задействовала в сражениях большое количество самолетов.