Al igual que su contemporáneo Pachelbel, fue instruido por Heinrich Schwemmer y Georg Caspar Wecker; también probablemente estudió con Johann Dretzel. A la edad de 17 años estaba tocando el órgano durante los servicios en la iglesia Agustiniana. Fue organista desde 1673 en St. Walburg auf der Veste, desde 1686 en la Frauenkirche y desde 1687 hasta su muerte en la Egidienkirche. Las suites en sus dos volúmenes llamados "Muth-und Geist-ermunternde Clavierlust (1679-1680) siguen las tradiciones de la escuela de Nuremberg, pero también presagian en un modesto nivel ciertas características técnicas típicas del desarrollo posterior de la suite para teclado.

Schultheiss fue el primer compositor alemán en adoptar lo que más tarde se convirtió en el orden estereotipado allemande-courante-sarabande-gigue, a los que añadió un preludio en las cuatro suites de la colección de 1679. El pedía que 'las allemandes y sarabandes fueran tocadas más bien lento, y las courantes y gigas más bien rápido y más frescamente', de modo que por el cambio de tempo de las suites pudieran 'complacer sentimientos sinceros'. Una conexión tipo variación entre los movimientos de una suite es a veces sugerido, pero todavía no es un dispositivo estructural consciente. Schultheiss escribió sus suites para un círculo burgués de aficionados y deseaba llenar un vacío con ellos 'ya que hasta ahora pocas de estas piezas para teclado se han publicado'. La baja opinión que de ellos tiene Seiffert se basa en un criterio equivocado, ya que los comparaba con obras virtuosas más ambiciosas escritas por músicos profesionales para clientes aristocráticos.

Las suites son la única música secular conocida de Schultheiss. Después se incorporó, probablemente alrededor de 1680, al grupo de intelectuales y artistas conocidos como el 'Pegnesische Blumenorden', que estaba interesado principalmente en cantos sagrados, y contribuyó con 40 melodías con continuo a las colecciones publicadas por este círculo. Estas canciones con continuo son tipo aria y las líneas vocales se mueven principalmente en corcheas determinadas por el ritmo de las palabras, con figuración ocasional de semi corcheas y secuencias. Schultheiss también publicó en 1682 cantos sagrados 'orquestales' con sinfonías introductorias.