In 1982 he was appointed head coach of East Germany after years working as assistant coach and head coach of the Under 21s.
After a successful six-year spell with the national team, Stange returned to FC Carl Zeiss Jena, now in the unified German Bundesliga and later moved to coach Hertha BSC where his old ties as an informant for the East German police, the Stasi, surfaced. He was an 'Inoffizieller Mitarbeiter', which translates as 'unofficial employee'. His code name was 'IM Kurt Wegner'. His tasks included informing the Stasi about his players' views of the government and whether any of them were breaking the law by making contact with West Germans. He was sacked after these allegations surfaced.
In 1998 he joined Perth Glory in the Australian National Soccer League. Glory under Stange in 2000 won the NSL league title however failed in the Grand Final, losing on penalties to the Wollongong Wolves after leading 3–0 at half-time. Stange was very popular among supporters in Perth to the point where a demonstration was held to prevent him from being sacked. However, his abrupt nature with players and other club officials made him a number of enemies, leading to his departure at the completion of his contract.
In 2001, he was given the opportunity to guide Oman to the 2002 FIFA World Cup Korea/Japan but was fired after less than three months in the job, just enough time for the German to attract the attentions of Iraqi sports officials, after his team beat Iraq 1–0.
Amid threats from the US President George W. Bush of a possible military conflict with Iraq, he arrived in Baghdad in October 2002 and put pen to paper to a 4-year contract that included two clauses allowing him to leave in the event of war and to refuse any political comment.
In 2005 Stange joined Apollon Limassol in Cyprus and helped them to avoid relegation. The following season Apollon won unbeaten the Cypriot Championship after 12 years. Also, Apollon won the Super Cup a few months later for the first time. Stange had indicated that he would not be continuing in Cyprus after the end of the 2005–06 regardless of results. However, after the success he had with the club, he continued for the 2006–07 season but resigned in the middle of that season because his team was not doing well and lost its chance to win the Championship again.
On 30 July 2007, Stange was appointed by the Belarus Football Federation to coach the national team after previous manager Yuri Puntus resigned the month before due to a poor performance in the Euro 2008 qualifying. For his first game on 22 August, against Israel, Stange, to the surprise of fans and media called up many young players from the domestic league, leaving veterans such as Denis Kovba out of the rosters for the game. His debut ended in a 2–1 impressive victory despite questionable positioning of players on the field (e.g. Dmitri Mozolevski, striker, playing as a defender). With Stange, Belarus achieved its highest FIFA rating in its history, currently being ranked at 55th.
On 7 October 2011, Belarus coach Bernd Stange stood down from his post after the end of the UEFA EURO 2012 qualifying campaign.
Bernd Stange has often commented on his desire to eventually settle in Perth with his wife Dorothea.