Граф вернулся в Энген, где продолжил работать служащим в местном муниципалитете. Тем временем ситуация в Германии менялась, и быстро увеличивавшимися в размерах Люфтваффе требовалось все больше пилотов. Появились и некоторые дополнительные родственные связи. В итоге Графа в 1938 г. приняли на действительную службу в Люфтваффе и направили в авиашколу.

31 мая 1939 г. унтер-офицер Граф прибыл в 2./JG51. Эскадрилья была вооружена Bf109E и размещалась тогда на аэродроме Бад-Айблинг, в 48 км юго-восточнее Мюнхена. Затем 28 августа она перебазировалась в Ойтинген, около северо-восточной окраины г. Пфорцхайм.

После того как 3 сентября Франция и Великобритания объявили войну Германии, пилоты 2./JG51, включая Графа, уже получившего звание фельдфебеля, начали совершать патрульные полеты вдоль французско-немецкой границы. 30 сентября эскадрилью перевели на аэродром Шпайер. Там она провела всего пару дней и уже 1 ноября прибыла на аэродром Зандхофен, на северной окраине Мангейма.

Всего в течение осени 39-го года Граф выполнил 21 боевой вылет. Однако в условиях «странной» войны на Западе шансов отличиться у него было крайне мало. В начале 1940 г. его направили в офицерское училище, где он прошел дополнительное обучение, в том числе и в части общего образования. 1 мая он получил звание лейтенанта.

6 октября того же 40-го года Графа включили в 9./JG52, в составе которой он в будущем и добился всех своих успехов. Эскадрилья тогда находилась в Нойруппине, но уже через несколько дней ее перебросили в Румынию, на аэродром Пипера, в нескольких километрах от северной окраины Бухареста. Там ее пилоты, включая Графа, в основном занимались обучением местных летчиков истребителей, помогая им освоить «Мессершмитты».

Затем 25 мая 1941 г. 9./JG52 перебросили уже в Грецию, на аэродром около городка Молаои, в 20 км северо-западнее порта Монемвасия. Она участвовала в операции «Меркурий» – захвате острова Крит. Взлетая с Пелопоннесского полуострова, ее пилоты тогда главным образом наносили штурмовые удары по позициям британских и греческих войск на Крите.

12 июня эскадрилья вернулась обратно в Румынию, на аэродром Пипера, а потом 21 июля перебазировалась на аэродром Мизил. С началом боевых действий на Восточном фронте ее «Мессершмитты» прикрывали румынские нефтепромыслы от возможных налетов советских бомбардировщиков. Части Вермахта тем временем продвигались все дальше на восток, и потому 1 августа эскадрилья перелетела на Украину, на аэродром около города Белая Церковь.

Ранним утром 4 августа десять Bf109F из 9./JG52 прикрывали группу Ju87B/R, атаковавшую позиции советских войск юго-восточнее Киева. Граф со своим ведомым унтер-офицером Леопольдом Штейнбатцем барражировал над «Штуками», когда на малой высоте появились И16. Заметив противника, он сразу же спикировал и сбил одну из «крыс», одержав свою первую победу.

На следующее утро эскадрилья вылетела на «свободную охоту» в район украинской столицы. Там она снова сошлась в бою с И16. Граф атаковал противника снизу, но тут же сам был сзади обстрелян другим советским истребителем. Получив несколько попаданий, он резко отвернул в сторону. Вероятно, пилот «ишака» не успел среагировать и, проскочив вперед-верх, попал под пушечный залп Графа. Загоревшись, И16 врезался в землю в паре километров южнее Киева. В том же бою немецкий летчик еще раз попал под огонь, и его Bf109F получил новые попадания. Тем не менее для Графа все завершилось благополучно, и он вернулся на свой аэродром.

7 августа пилоты 9./JG52 в очередной раз вылетели на «свободную охоту» в район Киева. Этот вылет едва не стал последним для Графа. В бою с И16 будущего кавалера Бриллиантов фактически спас его ведомый Штейнбатц, который вовремя сбил «крысу», висевшую у него на хвосте.

Днем 11 августа эскадрилья прикрывала Ju87, бомбившие мост через Днепр около города Канев. Две «Штуки» получили повреждения, и пара Граф – Штейнбатц получила приказ сопроводить их до аэродрома. Прямо над Днепром они были атакованы сзади МиГ3. Граф отвернул в сторону, а потом сам сел на хвост проскочившему вперед истребителю. Приблизившись на дистанцию около 50 метров, он открыл огонь, и «МиГ» почти вертикально рухнул на землю.

Когда 9./JG52 базировалась на аэродроме в Белой Церкви, Граф, да и не только он, испытал сильнейшее потрясение. 8–19 августа айнзатц-команда СС при помощи украинских националистов рас стреляла около этого города несколько сотен евреев. Летчики и меха ники эскадрильи, узнав об этом, испытали шок.

Впоследствии воспоминания об этой ужасной в бойне Белой Церкви периодически сплывали в памяти Графа. Он и до этого достаточно критически относился к политике нацистов в отношении евреев, вспомнить хотя бы его действия в бытность работы в муниципалитете Энгена. Можно утверждать, что события августа 1941 г. оказали значительное влияние на его поступки в послевоенный период, о чем будет рассказано ниже.

17 августа эскадрилья перебазировалась на полевой аэродром около поселка Сигнаевка, в 10 км северо-восточнее г. Шпола. 22 августа Графа наградили Железным Крестом 2-го класса. Число его побед постепенно росло. 27 августа 9./JG52 переместилась еще дальше на юго-восток – на полевой аэродром около станции Счастливое, в 23 км юго-восточнее г. Александрия. И утром 30 августа Граф в районе Днепропетровска сбил двухмоторный ДБ3.

Уже 2 сентября эскадрилью перевели на аэродром Мироновка. Вечером 6 сентября ее по тревоге подняли в воздух. Советские ДБ3 бомбили переправу через Днепр, которую в районе Кременчуга навели немецкие саперы. Оказалось, что И16 сопровождали бомбардировщики. В ходе боя, проходившего восточнее Кременчуга, Граф записал на свой счет еще один И16.

12 сентября 9./JG52 перебазировалась в Берислав, и на следующее утро Граф в бою северо-западнее Перекопа сбил Як1. Уже через два дня – 15 сентября – эскадрилью перебросили в Кременчуг, но и там она задержалась ненадолго. 17 сентября она перелетела на полевой аэродром около поселка Градижск, юго-западнее Кременчуга, а на следующий день вернулась в Белую Церковь.

Наконец, 24 сентября ее «Мессершмитты» приземлились в Полтаве. Вскоре после полудня того же дня Граф пополнил свой счет, сбив около г. Балаклея бомбардировщик ДБ3Ф.

Действуя из Полтавы, пилоты 9./JG52 регулярно прикрывали бомбардировщики и «Штуки», летавшие бомбить советские аэродромы около Харькова. Во второй половине 27 сентября они в очередной раз сопровождали Не111, атаковавшие харьковский аэроузел. Уже на обратном пути немцы заметили, что вслед за «Хейнкелями» пристроилась еще какая-то группа двухмоторных самолетов. Это были ДБ3Ф из 8-го БАП, чьи экипажи, видимо, надеялись незамеченными достигнуть аэродрома немецких бомбардировщиков и сбросить свои бомбы сразу же после их приземления.

«Мессершмитты» сразу же атаковали противника. По данным Люфтваффе, было сбито пять бомбардировщиков, один из которых был на счету Графа. Однако и его Bf1090F тоже досталось, – снаряд одного из бортстрелков попал в двигатель. Наружу брызнуло масло, мощность мотора быстро падала, но пилот все же смог дотянуть до своего аэродрома.