Stavrum startet sin fotballkarriere i Clausenengen i hjembyen Kristiansund. I 1991 gikk han til Brann, hvor han ble lagkamerat med sin bror. Arild Stavrum gjorde aldri noen stor suksess i Bergen, og ble solgt til Molde etter 1993-sesongen.
I Molde ble Stavrum en desto større suksess. I 1994 ble han klubbens toppscorer, da Molde rykket opp i Eliteserien igjen etter én sesong på nest høyeste nivå. Molde ble også cupmestere denne sesongen. Året etter scoret Stavrum 16 Tippeligamål da Molde, anført av «de tre S'ene» (Stavrum, Solskjær og Sundgot) tok sølv i serien.
I 1997 ble Stavrum solgt til Stabæk. Etter én sesong ble han kjøpt av den svenske klubben Helsingborg, der han ble gjenforent med sin gamle trener i Molde, Åge Hareide. I sin første sesong i Helsingborg, ble Stavrum toppscorer i Allsvenskan med 18 mål. Sesongen etter ble han svensk seriemester, og var nok en gang klubbens toppscorer. Ved sesongslutt ble han kjøpt av den skotske klubben Aberdeen.
Stavrum spilte to sesonger i Aberdeen, og ble klubbens toppscorer begge sesongene. Sommeren 2001 meldte han overgang til tyrkiske Besiktas, der han spilte to sesonger før han i 2003 returnerte hjem til Molde. I løpet av sitt andre opphold i Molde var Stavrum mye plaget av skader, og huskes mer for sine mange, og til dels kontroversielle, utspill om Rosenborg enn for sine prestasjoner på banen.
Stavrum la fotballskoene på hylla etter 2004-sesongen, og tok fatt på trenerjobben i Bærum. I sin eneste sesong som trener for bæringene, ledet han klubben til en fjerdeplass i 2.divisjon, avdeling 1.
Stavrum var tilbake som hovedtrener i Molde FK i 2006 sesongen, etter et hvileår bak i kulissene i 2005. Dette året førte han Molde FK ned til Adeccoligaen. Har i den senere tid jobbet mye for TV2-sporten som reporter under Tippeligarunden. Ellers har Stavrum i flere år skrevet en månedlig spalte i fotball- og tegneseriebladet BOING, en klubb for fotballgale gutter og jenter.
Karriere som spiller
| Klubb | Kamper* | Mål* | Periode |
|---|---|---|---|
| Clausenengen | ? | ? | ????-1990 |
| Brann | 25 | 3 | 1991-1993 |
| Molde | 73 | 45 | 1994-1996 |
| Stabæk | 26 | 7 | 1997 |
| Helsingborg | 52 | 29 | 1998-1999 |
| Aberdeen | 54 | 26 | 1999-2001 |
| Besiktas | 18 | 5 | 2001-2002 |
| Molde | 27 | 1 | 2003-2004 |