Po rezygnacji Rudiego Völlera z funkcji trenera reprezentacji Niemiec z powodu odpadnięcia już w pierwszej rundzie portugalskiego czempionatu, Rehhagel był rozważany jako jeden z najsilniejszych kandydatów do objęcia funkcja selekcjonera reprezentacji swojej ojczyzny. Miał wsparcie kibiców, pomimo niezbyt dużego zaufania środowiska piłkarskiego. Kiedy trzech pozostałych kandydatów odrzucono Rehhagel otrzymał oficjalną propozycję, którą odrzucił 10 lipca 2004 roku.
W Grecji Rehhagel zwany jest także Królem Otto (βασιλιάς Όθων), możliwe, że wynika to ze zbieżności imion z pierwszym królem Grecji, jednak ten pseudonim został mu nadany już podczas pracy w Niemczech. Grecy lubią go porównywać również do mitologicznego Heraklesa, nadając mu pseudonim "Rehakles".
Grecja, trenowana przez Rehhagela zajęła trzecie miejsce w swojej grupie eliminacyjnej do niemieckiego mundialu, przez co nie awansowała do niego. Później awansował jeszcze z Grecją do Euro 2008 i Mundialu 2010. Oba turnieje zakończyli po fazie grupowej.