Sus padres murieron poco después de su nacimiento y él creció entre amigos, hermanos y hermanas. Comenzó su formación musical con clases de canto bajo los Kantors de Wertheim. Entre 1701 y 1703 fue alumno en la Heiliggeistschule en Nuremberg, luego se trasladó a Worms y, entre 1706 y 1708 vivió en Frankfurt, donde asistió al Gymnasium. Después de regresar a Nuremberg en 1708 viajó extensamente por Bohemia y Sajonia hasta Hamburgo y Harburg, donde pasó un año; desde allí viajó a través de Lüneburg a Baja Lusacia, a través de Dresde a Bohemia y Moravia, y finalmente a través de Baviera a Salzburgo.

No tuvo éxito en su intento de completar sus estudios musicales en Italia. Después de algún tiempo en Regensburg y Altdorf (donde jugó con la idea de estudiar teología), regresó a Nuremberg. Allí recibió instrucción en composición del Kantor de la Heiliggeistkirche, Nikolaus Deinl, y tocó en el 'collegia musica' (teclado, flauta, corno e instrumentos de cuerda). En 1711 se convirtió en Kantor en Sulzbach, Alto Palatinado, y en 1714 fue nombrado Kantor y tutor en el Gymnasium Poeticum de Regensburg. Después de 50 años en el cargo fue presentado con un ‘Festschrift’ (conmemorativo) y una cantata en su honor, con música de su hijo, Carl Ehrenreich (1721-1785).

Las obras de Stolzenberg (según su autobiografía) incluyen un ciclo completo de cantatas para el año de la iglesia, escrito durante su tiempo en Sulzbach; cada obra en este ciclo 'comienza con un texto bíblico (por lo general en fuga), continúa con varias arias, y concluye con una coral'. Más tarde compuso muchos otros ciclos anuales, en los que se utilizaron recitativos.