Leider liegen aus der Errichtungszeit der Kirche keine Urkunden vor, sodass man hier nur schätzen kann. Man geht davon aus, dass die Erbauung der Nikolauskirche am Heimenstein in die Zeit des 11.-12.Jahrhunderts fällt. Zu dieser Zeit, am 9. Mai des Jahres 1087, wurden die Reliquien des heiligen Nikolaus aus Kleinasien nach Bari in Italien gebracht. Ihm zu Ehren wurden in dieser Zeit an vielen Orten Kirchen errichtet. Dies geschah auch in Deutschland. So ist zum Beispiel bekannt, dass schon im Jahre 1151 in Eisenach eine Kirche seinen Namen trug. Man darf also mit einiger Sicherheit annehmen, dass etwa in diese Zeit auch die Errichtung der Nikolauskirche im damaligen Marktflecken Heiligenstadt fällt. Vermutlich wurde hier auch einer der berühmtesten Söhne Heiligenstadts getauft, der Bildhauer und Bildschnitzer Tilman Riemenschneider (etwa 1460 in Heiligenstadt geboren). Dessen Geburtshaus – die heutige Klausmühle – ist nur wenige Meter entfernt in der Klausgasse zu finden.

Von der einstigen Kirche St.Nikolaus  ist heute nur noch der Altarraum erhalten, der nach außen abgeschlossen und mit einer Tür versehen worden ist. Von den Umfassungsmauern sind heute noch Reste zu erkennen, die die frühere Größe feststellen lassen. Danach bestand das Bauwerk aus einem rechteckigen Schiff von 13,50 m Länge und 9,10 m Breite. Das alte spitzbogige Westportal bildet heute den Zugang zu einem Vorhof.