Soltvedt started his professional career at Viking in Stavanger in 1987 and was a member of the team who won the Norwegian Cup in 1989 and the Tippeligaen in its inaugural year, 1991. In 1992, he joined mid-table club Brann. At the end of his first season he was voted the club's "most popular" player. During his time at Brann, the club finished each season in 6th or 7th place in the league. His extremely dedicated style, his innocent and somewhat naïve personality and the fact that many of his goals were scored as a midfielder made him immensely popular. Just before the start of the 1995 season, however, he was sacked by Brann's board for "illoyality", the board refusing to elaborate on this. This prompted a demonstration from fans supporting Soltvedt. After three seasons at Brann, he moved to Rosenborg where he was able to share in more success, claiming the Tippeligaen championship in 1995 and 1996 as well as winning the Norwegian Cup in 1995. Trond Egil was also part of the Rosenborg team who beat AC Milan 2-1 away at the San Siro to advance to the quarter-finals of the Champions League.
England
His success in Norway brought him to the attention of English clubs and after an unsuccessful trial at Stoke City, Gordon Strachan signed him for Coventry City for a fee of £500,000 in July 1997. After two seasons at Coventry City, he was then signed by Southampton under Dave Jones in August 1999 for £300,000. He was a "tall, elegant midfielder who added an air of calm authority whenever he played". He made his Saints debut as a substitute in a 4-2 victory over Newcastle United on 15 August 1999, helping to set up Mark Hughes for the final goal. He made a total of 24 appearances in the 1999-2000 season, playing in midfield alongside Matthew Le Tissier and Marians Pahars as Saints struggled both in defence and in attack, finishing in the lower half of the table. Soltvedt missed a large part of the last few months of the season with persistent groin problems. After replacing Jones as Southampton's manager, Glenn Hoddle soon transferred Soltvelt to Sheffield Wednesday, initially on loan before making the deal permanent in March 2001 for an appearance-based fee which had the potential to rise as high as £200,000. He remained at Sheffield Wednesday for three seasons and was appointed team captain. Unfortunately, he was unable to prevent Wednesday being relegated at the end of the 2002-03 season, when he was released, returning to Norway to play in the lower leagues.
