In an unusual football experiment, the board of the Club, as well as its usual processes in looking for a new manager, took account of the views of supporters in selecting Steve. In December 2002 Paterson took up the reins at Pittodrie and began the challenging process of restructuring his playing squad whilst working withing tough budget constraints.
In that first season, the team had been struggling to find any kind of winning form, and were firmly placed in the lower part of the League table. However, by April Steve took the team into a winning run which pushed them up the table.
Unfortunately personal problems intervened and Steve missed a home match against Dundee in March 2003, with Duncan Shearer taking charge on the day. The club stuck by the manager and sought to help him and he remained in post for a further season. That season turned out to be a very poor one for the Dons who finished in 11th position of the League and shortly after the season ended Steve was dismissed from his post.