After three seasons with Dundee United he came to the attention of West Ham United. Turning down an initial bid of £175,000 he transferred to West Ham for a fee of £430,000 in 1979 making him the most expensive teenage footballer at the time. Stewart made his West Ham debut on 4 September 1979, playing as a defender, in a League Cup game against Barnsley. His first West Ham goal, a penalty, came on 29 September 1979 in a 2–1 home win against Burnley. In 1980 West Ham won the FA Cup. Stewart was West Ham's top scorer playing a vital part in their victory, including two goals in the fourth round against Leyton Orient and a last minute penalty winner in the quarter-final against Aston Villa. In the semi-final replay on 16 April 1980, against Everton, Stewart was moved into central defence replacing an injured Alvin Martin. The following season Stewart was a vital member of the team which won the 1980–81 Football League Division Two, playing 41 games and scoring five goals, all penalties. Renowned for his ability as a penalty taker he scored 81 out of 86 with only one miss on his home ground. His penalty taking technique involved him striking the ball with force with his right foot, with Stewart ending-up with both feet off of the ground. From his five misses he scored twice from the rebound. One of his penalties came in the 1–1 draw with Liverpool in the 1981 Football League Cup Final, West Ham however lost the replay.
Stewart continued to be an important member of the West Ham side throughout the 1980s including scoring six goals, again all penalties, in their highest finish of third, in the Football League in 1985–86; a season in which he finished third highest scorer for West Ham behind Tony Cottee and Frank McAvennie. In 1989, with West Ham fighting a relegation battle, Stewart suffered a serious injury in the first half of a game in January against Derby County. He ruptured two of the four ligaments around his knee including the main anterior cruciate ligament. He was out-of-action for fourteen months. He returned in a reserve team game in March 1990 and played seven game in a month in a bid to get fit. This proved to be too many games and he needed a further operation on his knee. He returned for the beginning of the 1990–91 season having been recalled by new West Ham manager, Billy Bonds. His injury, along with further problems with hamstring injuries, meant his appearances became fewer with none at all between January 1989 and April 1991. He made a substitute appearance in West Ham's 4–0 1991 FA Cup semi-final defeat to Nottingham Forest on 14 April 1991 coming on to replace Martin Allen and just five in the West Ham side which won promotion from the 1990–91 Second Division. His last game came on 4 May 1991 in a 1–1 draw at Selhurst Park against Charlton Athletic Following his run of injuries, aged 31, Stewart was not offered a further contract and was released on a free transfer.
Stewart scored 84 goals, all but six being penalties, in 434 games for West Ham. Despite playing in defence he was sent off only twice in his West Ham career, neither for fouls committed but on both occasions for comments made to referees or linesmen in games against Aston Villa and Liverpool. He is also notable to be the only non-English player to appear for West Ham United in any of their three FA Cup winning sides of 1964, 1975 and 1980. He became a favourite with the fans who nicknamed him "Tonka" after Tonka Toys, which were described as 'indestructible'.