Han blev 1984 bäste målskytt i Gais, trots att han var mittback och blev utsedd till årets makrill. Sjöstedt gick från Gais till Öis 1987 och stannade kvar i klubben fram till 2000 då han avrundade karriären med spel i Västra Frölunda IF och Superettan.
Under sin tid i Öis utmärkte sig Sjöstedt som en stabil och pålitlig försvarare. Han var lojal mot klubben, trots spel i division 1 och 2 i början av 1990-talet stannade han kvar. Han var under de sista åren lagkapten och gick bland supportrar under namnet "Kung Sjöstedt". Under sin sista säsong kunde han gå om Carl-Erik Holmberg och bli Örgryte IS meste allsvenska spelare med 261 matcher. Han blev dessutom Svensk cupvinnare2000.
