Nordlie is a household name in Norway, having managed several top-flight teams. He is known for introducing the concept kontrollert sinnsyk, i.e. "controlledly insane".
In 1998, he led Odd Grenland to promotion to the Norwegian Premier League, and to a respectable seventh place the next season. In 2000, he took over big club Vålerenga, but was fired after a season that led to Vålerenga's relegation from the Norwegian Premier League. After working as a football expert in TV 2 for a while, Nordlie was hired as coach of Sandefjord. He led the club to the promotion play-offs in both 2002 and 2003, but lost both times. In 2004 he took over the struggling Start, and in his first season in charge, Start won the First Division and were promoted. In their return to Tippeligaen, Start had a great spring season, and won the silver medals, only one point behind winners Vålerenga. For this feat, Nordlie won the Kniksen award as (Head) Coach of the Year.
However, in 2006 Start had a poor opening to the season, and on 14 July 2006, Nordlie was fired. After working in TV 2 for a short period, Nordlie signed as the new manager of Viking on 14 September for the rest of the 2006 season, saving Viking from being relegated to the First Division, when Viking beat Brann 5–0 in the last match of the 2006-season.
After Lillestrøm fired Uwe Rösler, Nordlie was hired on 16 November. In his first season (2007) at Lillestrøm Nordlie achieved a fourth place in the league, and won the Norwegian Cup, LSK's first real trophy in 18 years. The following 2008 season started off disappointingly for Nordlie and LSK, and after 8 matches, and only 6 points, Nordlie was sacked on 29 May. In August the same year he was hired as a manager for struggling second-tier side Kongsvinger, which he led with success until he was hired by Fredrikstad in August 2009. He had some months at the club who were battling against relegation when he arrived. By the end of the season Fredrikstad were relegated, after being beaten by local rivals Sarpsborg 08 in the play-offs. Nordlie left a few months after the relegation.
Nordlie returned to Kongsvinger in September 2011, after Per Brogeland was fired, to save the club from relegation to the Second Division. The club was 11th, two points ahead of the relegation zone when Nordlie arrived, and finished the season as the 7th best team in the First Division. He originally joined Kongsvinger on a short-term contract, but decided to stay at the club for another year, before he left Kongsvinger after the 2012 season.