Stölzel was born in Grünstädtel, in the Erzgebirge, on 13 January 1690. His father, organist in Grünstädtel, gave him his first music education. When he was thirteen, he was sent to study in Schneeberg, where he was taught music, including thoroughbass, by cantor Christian Umlaufft, a former student of Johann Kuhnau. A few years later he was admitted to the gymnasium in Gera, where he further practiced music under Emanuel Kegel, the director of the court chapel. Some of his educators took a dim view of music, and tried to divert his attention from it: apart from engaging in poetry and oratory, Stölzel nonetheless continued to develop his interest in music.