Легендарная карьера Руделя началась только после переброски его части на Восточный фронт. Первое боевое задание Рудель выполнил в составе I./StG2 в 03.00 23 июня 1941 г. В тот день до заката он совершил четыре боевых вылета. Летом "короли воздуха" без противодействия практически непрерывно висели над нашими отступающими войсками и беженцами, иногда неделями совершая до восьми боевых вылетов в день.

В один из июльских дней подбитый зениткой напарник Руделя совершил вынужденную посадку на территории противника. Рудель попытался приземлиться рядом и вывезти экипаж, но сам получил с земли пулеметную очередь в маслорадиатор. Вместо подвига пришлось думать о собственном спасении, он еле-еле перетянул через линию фронта. За первую неделю войны его эскадра StG2 потеряла 14 "штук", а 24 июля он совершил свой 100-й боевой вылет.

18 августа на выходе из пикирования при атаке железнодорожной станции Чудово Рудель "побрил" верхушки берез и привез на аэродром "дрова". Тогда новый командир III./StG2 гауптман Э.-З.Щтеен, которому смелый пилот приглянулся, сказал о "Руделе: "Он - лучший в моей группе! Но этот сумасшедший долго не проживет"

В сентябре 1941 г. на долю Руделя пришелся один из самых больших успехов немцев на Ленинградском фронте. Две группы его эскадры перебазировались на аэродром Турково под Лугой, откуда летали бомбить Ленинград и корабли в Кронштадте. Утром 23 сентября три эскадрильи со специально доставленными из Германии бронебойными 1000-кг бомбами PC1000RS, взяли курс на гавань Кронштадта, где находились главные силы Балтийского флота, в том числе линкоры "Октябрьская революция" и "Марат". "Штука" Руделя шла в головном звене прямо позади машины назвавшего его сумасшедшим комэска.

Как вспоминал Рудель, был ясный день - безоблачное голубое небо, не "омрачили" его и советские истребители. На высоте 3000 м примерно в 15 км от Кронштадта немцев встретил шквал зенитного огня. Рудель написал, что "он был убийственным, Иваны не стреляли по отдельным самолетам, а создавали заслон... Если бы это не было так опасно, я мог бы описать это как карнавал в воздухе". Пытаясь уклониться от огня, "штуки" перемешали строй, но Рудель как привязанный следовал за хвостом командирской машины. Когда тот выпустил тормозные щитки, Рудель последовал за ним в пике с углом 70-80°. С пронзительным ревом пикируя на "Марат", Рудель увидел, что комэск убрал щитки и снова повторил его действия. Скорость обеих "штук" резко увеличилась и, к очевидному ужасу стрелка ведущего, чье лицо было впереди всего в нескольких метрах, самолет Руделя стал догонять переднюю машину. Чтобы не столкнуться, Рудель отдал от себя ручку и увеличил угол пикирования, начав падать практически отвесным. Едва не столкнувшись с ведущим, летчик увидел, что теперь ему навстречу летит огромный "Марат" с матросами, суетившимися на палубе. На высоте 300 м, удерживая корабль в прицеле, Рудель нажал кнопку сброса бомбы и одновременно сильно потянул ручку на себя. Перегрузка на выходе из пике настолько превысила допустимые пределы, что летчик на несколько секунд потерял сознание. Когда оно вернулось, он обнаружил свой самолет летящим всего в 3-4 м над водой и услышал стрелка, возбужденно кричащего по переговорному устройству: "Корабль взорвался!... Ты должно быть попал ему в артиллерийский погреб". Действительно, серо-черное облако поднялось на высоту полкилометра, силой взрыва корабль раскололся надвое, и носовая часть сразу же затонула. "Из спортивного интереса" Рудель страстно желал попасть и в другой линкор -"Октябрьскую революцию". И однажды это ему якобы удалось, но 1000-кг бомба не взорвалась!*

В октябре Hl./StG2 перебросили на центральный фронт. Осень и начало зимы в том году в России были очень суровыми, в ноябре температура по ночам опускалась до -40°С. Эскадра Руделя базировалась в районе Смоленска, и в его мемуарах значительное внимание уделено тем трудностям, с которыми встретились немцы, летая и обслуживая самолеты в таких условиях. Количество исправных машин в эскадрильях резко упало, двигатели днем и ночью прогревали каждые полчаса, накрывая капоты соломой и одеялами. Резко сократилось число летных дней из-за туманов и снегопадов. Однажды, потеряв в тумане ориентировку, Рудель пошел на вынужденную и попытался "дорулить" до своего аэродрома, пока не уткнулся в железнодорожный переезд. В тот же день он был в воздухе на другой машине.

24 сентября 1942 г. Рудель первым среди пилотов штурмовой авиации совершил 500-й боевой вылет. В январе 1942 г. Руделя направили в краткий отпуск, затем послали передавать боевой опыт в школу летного мастерства в Граце. Здесь он увлеченно занимался любимыми видами спорта - метанием диска и копья, и толканием ядра. Он оставался убежденным трезвенником, позже за ним по пятам ходила поговорка: "Major Rudel trinkt nur sprudel" (Майор Рудель пьет только минеральную воду).

В Граце "летно-спортивные" тренировки продолжались до июня 1942 г., пока он вновь не попал в свою старую летную группу на Северо-Кавказском направление. По пути Рудель переболел желтухой, но, не долечившись, продолжал летать. "В этот игре, - говорил он сам себе, - ты не можешь себе позволить слишком долго не быть в боях, ты можешь пропустить какую-нибудь новую тактику противница или самолет". Вновь ежедневное число боевых вылетов доходило до восьми, а 22 ноября Рудель стал командиром 1-й эскадрильи I/StG2, совершая невероятное количество боевых вылетов, тем более что наступавшие советские танки почти подошли к их аэродрому. Утверждали, что в течение 25 ноября обер-лейтенант Рудель бомбил подошедшие к своему аэродрому танки не менее 17 раз!

10 февраля 1943 г. в районе Изюма он совершил 1000-й боевой вылет и стал широко известным в Германии. Для восстановления сил после болезни Рудель получил двухнедельный отпуск, затем его направили в Брянск для испытаний новых противотанковых "штук", сведенных в специальное соединение. В битве на Кубани первыми целями противотанковых 37-мм авиационных пушек стали десантные суда на Черном море. Руделю на самолет установили кинокамеру, пленки позже демонстрировали в выпусках немецкой кинохроники. Подсчитали, что Рудель в течение трех недель потопил около 70 мелких судов.

* Позже утверждали, что все однотонные бомбы, доставленные в StG2, были с дефектами невыясненного происхождения и не взрывались.