Newman signed for Bristol City as an apprentice in October 1981 and played 483 games for the club, serving as club captain before being sold to Norwich City for £600,000 in 1991. He was a member of the Norwich team that finished a club record third in the FA Premier League in 1992–93 and went on to play a part in the defeat of Bayern Munich in the following season's UEFA Cup.
During his time with Norwich, Newman was initially used in 1991–92 as a central midfielder, where he managed to score several important goals. He even deputised as a forward covering for injuries. He was ultimately primarily played in central defence in the majority of games for Norwich, particularly later on in his career. Newman was noted for his determination, versatility and a very hard (if not always accurate) shot.
During a dead ball competition at Wembley in 1994, it was found that Newman had the hardest shot in the league at the time.
After his playing days, Newman became a manager in the lower leagues of English football. He had a short time spell at Southend United before being appointed assistant manager to Steve Thompson at Cambridge United in December 2004. Following Thompson's departure from an unsuccessful spell which led to Cambridge's relegation from the Football League, Newman was appointed manager in May 2005.
Newman built a squad with very little money and showed his abilities in scouting little-known players. He also gained the support of the majority of Cambridge fans, earning him the nickname of 'Buzz Lightyear', owing to his facial likeness to the character from the motion-picture Toy Story. Some fans even set up a fan site (see below), and wore Buzz Lightyear masks in homage to him.
However, he was sacked following United's 3–1 defeat by Exeter City on 1 September 2006 that left the club second-bottom of the Conference.
The following month, the new Bournemouth manager Kevin Bond appointed Newman as his assistant. Newman also played for the Bournemouth reserves team. Most of the time, it was when Reserve Team Manager Eddie Howe played a youthful side to help stabilise the defence. Occasionally, he was included in Bournemouth first team, being named a sub in the match against Carlisle after the team had only 14 fit first team players. He made his Bournemouth début away to Bristol Rovers in a Football League Trophy South Section Area Second Round match, appearing as a substitute. Bournemouth went on to win the match 1–0. Newman was sacked along with Kevin Bond and Eddie Howe in September 2008.
Newman is currently head of Manchester City's Spanish scouting team.