In Iceland

Guðjón's last season as a player was 1986 and his first coaching job was at ÍA Akranes in the 1987 season. Guðjón then left off to Akureyri to become manager of KA Akureyri in 1988. The team won its first and only league title surprisingly in 1989. That has to be known as a big achievement for Guðjón given the players he had in his squad. After being relegated in 1990, ÍA Akranes appointed Guðjón as manager. The team was promoted at first attempt, and subsequently won the Icelandic league the following year, in 1992. The team dominated Icelandic football the next few years and became league champions of Iceland for five years running, 1992–1996.^[4]

KR Reykjavik, Iceland's oldest and most successful club, appointed Guðjón after the 1993 season. The team had not won the Icelandic league for more than 20 years and Guðjón was seen as the right man to win the title. He did not win the league in his two-year stint at the club, but the team did however win the Icelandic Cup on both occasions 1994 and 1995. Guðjón came back to Akranes after his spell at KR and guided the team to win the Icelandic league and the Cup in 1996. After the season, actually late in November 1996 ÍA Akranes terminated his contract. But Guðjón wasn't out of a job for too long. In June 1997 he took charge of the Iceland national team. Guðjón was successful as manager of the Iceland national team. During the three years he was in charge, the team played 24 games, winning ten of them, drawing four and losing eight. The team scored 35 goals in the process, conceding 23.

The team was close to qualifying to the European Championship in 2000, despite being placed in a strong qualifying group alongside Ukraine, Russia and current world champions France. The game that took place at Stade de France was one that put Icelandic football to a higher standard. After being 2–0 down at half time, to come back too 2–2, and closely losing in additional time 3–2.

Stoke City

Guðjón became Stoke City manager in November 1999, when he joined the club following the successful acquisition of the club by a group of Icelandic businessmen headed by Gunnar Gíslason.^[5] They decided to bring in their own man to replace the existing manager Gary Megson. Guðjón brought in a number of his fellow countrymen to the club with the arrival of Einar Daníelsson, Sigursteinn Gíslason, Brynjar Gunnarsson and his son Bjarni Guðjónsson. He got off to a perfect start as Stoke manager as his side beat Wycombe Wanderers 4–0 on 23 November 1999. Good results continued as more Scandinavian players arrived at the club such as Frode Kippe, Mikael Hansson and Arnar Gunnlaugsson.^[5] Stoke also reached the 2000 Football League Trophy Final where they faced Bristol City in front of 75,057 at Wembley. Goals from Graham Kavanagh and Peter Thorne earned Stoke a 2–1 victory. In the league Stoke finished in sixth position reaching the play-offs where they faced Gillingham. Stoke won the first leg 3–2 but two controversial refereeing decisions cost Stoke dearly and they lost the second leg 3–0.^[5]

In 2000–01 Guðjón was again busy bringing in Icelandic players with Ríkharður Daðason, Stefán Þórðarson, Birkir Kristinsson and Danish defender Henrik Risom all agreeing to move to Stoke-on-Trent. Results were often inconsistent meaning automatic promotion was not possible and Stoke made it into the play-offs.^[5] They faced Walsall who, after a 0–0 draw in the first leg, beat Stoke 4–2, meaning that Stoke faced a fourth season in the third tier. The pressure was on Guðjón to gain automatic promotion in 2001–02 and he tried a different approach. He sold both Graham Kavanagh and Peter Thorne to Cardiff City for a combined fee of £2.7 million and with that money he brought in defender Peter Handyside from Grimsby Town who was made captain, goalkeeper Neil Cutler, Belarusian defender Sergei Shtanyuk, Belgian midfielder Jurgen Vandeurzen, David Rowson from Aberdeen and most impressively former Dutch international Peter Hoekstra.^[5] Stoke were again lacking the consistency for automatic promotion and for the third season running they entered the play-offs. The opponents this time were Cardiff and it looked like being another failure as the Bluebirds won the 1st leg at Stoke 2–1.^[5] Stoke went into the second leg at the notoriously hostile Ninian Park 2–1 down and with both sides missing chances the match was 0–0 after 90 minutes and in the final minute of injury time James O'Connor scored to send the match into extra time.^[5] And Stoke scored again via an O'Connor shot which deflected in off Souleymane Oularé to give Stoke the most dramatic victory.^[5] The final against Brentford was not as dramatic, as Stoke won comfortably 2–0 thanks to goals from Deon Burton and an own goal from Ben Burgess.^[5] However, despite finally achieving promotion via the play-offs at the third attempt Guðjón's contract was not renewed.^[6]

Start

Guðjón signed a contract with Start^[7] in Kristiansand just through the end of the season to try to steer the club away from relegation. However relegation was inevitable. But at the time Guðjón spent there five of the young players in the squad were called up for the U21 Norway side for the first time.

Barnsley

Barnsley appointed Guðjón as manager in 2003. The club had a great start to the season, but his reign ended after a Peter Ridsdale takeover at the club. Guðjón was fired in 2004.

Keflavík

Guðjón decided to return to Iceland in 2005 and was appointed manager of Keflavik. However, he quit just three days before the first game of the season to take charge of Notts County.

Notts County

Guðjón was appointed manager of Notts County in 2005. The team started well, leading the table early on, but eventually failed to make the playoffs. Guðjón resigned his post at Notts County in May 2006 after Notts County finished in 21st place in League Two and in 89th place overall, the lowest position the club had ever finished. Guðjón became the club's first non-British manager when he arrived at Meadow Lane in May 2005.

ÍA Akranes

ÍA Akranes had a difficult season in 2006, avoiding relegation in the last few weeks of the season. Guðjón was appointed manager ahead of the 2007 season, where the team finished third in the league, with one of the league's youngest teams and also scoring the third most goals in the league. In June 2008, the media in Scotland repeatedly linked Guðjón with the manager's post of Heart of Midlothian,^[8] with Terry Butcher as his assistant, but Akranes officials insisted it was only rumours and he would stay put in Iceland. Guðjón himself did, however, confirm to an Icelandic news-site that discussions with Hearts had indeed taken place^[9] and that he was considering his options. On 11 July, Hearts appointed Csaba Laszlo as the new manager.^[10] Whether Guðjón had ever been a serious contender for the job is not known.

On 21 July, Guðjón was fired from his post at ÍA.^[11] The team's performance had been going straight downhill for weeks, but the final straw was a 6–1 defeat against Breiðablik. Guðjón was replaced by the brothers, Arnar Gunnlaugsson and Bjarki Gunnlaugsson.^[12]

Crewe Alexandra

Guðjón was announced as new manager of League One side Crewe Alexandra on 24 December 2008, as a permanent replacement for the recently sacked Steve Holland. However, previous caretaker manager Dario Gradi remained in charge of the team for two games during the Christmas period, with Guðjón taking over on 29 December.^[13]

Despite improvements on the pitch, which saw him win manager of the month for February^[14] he could not prevent the club from being relegated into League Two. The poor form continued in the new season, and Guðjón was sacked as Crewe manager on 2 October 2009.^[15]

Later career

In July 2020, he took over as the manager of 1. deild karla club Víkingur Ólafsvík after the firing of Jón Páll Pálmason.^[16] Despite initial interest by both parties for him to continue with the team following the season, the team eventually hired Gunnar Einarsson. In July 2021, Gunnar was fired with the team in last place after the first nine games and Guðjón was hired again.^[17] His contract was not renewed after the team finished 7th in the 2. deild karla in 2022.^[18]