Rehhagel played for the local club Rot-Weiss Essen (1960-63), after the start of the Bundesliga for Hertha BSC Berlin (1963-65), and until 1972 for Kaiserslautern. He played 201 games in the Bundesliga.
He started to become a coach in 1974, with Kickers Offenbach and after several short assignments he worked for Werder Bremen from 1980 till 1995. During this spell, Werder Bremen established themselves as one of the main teams in the Bundesliga. He led them to two German championships, in 1988 and 1993 and two German Cup victories, as well as one win in the Cup Winners' Cup.
He coached Bayern Munich for little less than a year in the 95-96 season. He was famously ousted three weeks before they were to play in the final of the 1996 UEFA cup, after a disappointing end ot their league campaign. His position was taken by Franz Beckenbauer who led the team to victory in the cup. After this, he coached Kaiserslautern 1996-2000, winning a sensational German championship in 1998 directly after rising from the 2nd division.
In 2001 he became coach of the Greece National Football Team. The team qualified directly for the Euro 2004 cup, ahead of Spain and Ukraine. Ranked 100-1 outsiders, they sensationally defeated Portugal, France and the Czech republic, favourites to many on the way to the finals where they defeated Portugal again to lift the cup. Rehhagel, who was seen as the man most responsible for the team's success, became the first foreign coach ever to win a European Championship.
Rehhagel adopted a defensive approach in playing his Greek side, using energetic midfielders to weary the opponents and the policy of defending in numbers to numb opposition attacks. When charged with boring play, he said, "No one should forget that a coach adapts the tactics to the characteristics of the available players." Interestingly, his time at Werder Bremen is remembered for the flashy and spectacularly attacking football the team favoured.
After Rudi Völler resigned as Germany coach in the wake of that country's first-round exit in Euro 2004, Rehhagel was considered by many to be a strong candidate for his homeland's job. He had the support of the public, despite being considered a maverick by the footballing establishment. After three other candidates removed themselves from consideration, Rehhagel received an offer to take over as Germany coach, which he officially turned down on July 10.
After 2004, Rehhagel helped Greece qualify for the finals of two more major tournaments: Euro 2008 and World Cup 2010. After the latter campaign, on June 24, 2010, he announced his retirement to his players, bringing a nine-year reign to a close.
In Greece, he is occasionally called King Otto (βασιλιάς Όθων), probably in allusion to King Otto of Greece, however he already had this nickname during his coaching career in Germany. As a wordplay referring to Herakles, son of Zeus, he has been nicknamed "Rehakles" as well.
Rehhagel returned to coaching in February 2012, at the helm of his former club Hertha Berlin.
- According to Greek newspaper Eleftherotypia, Otto knows how to say two things in Greek. The phrase «σήμερα είναι μία ωραία μέρα» (today is a nice day) and the Greek national anthem.