1306 taucht ein Johannes dictus Stenhouel auf. Das Dorf selbst wird 1375 erstmals im Landbuch erwähnt. Dort finden wir zwei wichtige Informationen. Einmal dient Steynhovel, was so viel wie „steiniger Hügel“ bedeutet, auch der Versorgung der Burgbesatzung von Greiffenberg. So sitzt hier der Adlige Bertram von Greiffenberg und dazu noch 4 Burgmannen. Zusammen verfügen sie über 18 Freihufen. Sonst aber ist es um das Dorf nicht sonderlich gut bestellt. Von den 54 Hufen werden nur noch 16 von Bauern bearbeitet und auch die Hälfte der 20 Kossätenstellen ist unbesetzt. Die wirtschaftliche Lage in der 2. Hälfte des 14. Jahrhunderts ist nicht sonderlich günstig.

Als Steinhöfels Kirche um die 100 Jahre zuvor erbaut wurde, muss es noch anders ausgesehen haben. Es ist ein relativ großer Rechtecksaal, errichtet aus Lagen sorgfältig bearbeiteter Feldsteinquader. Drei Portale, eins im Westen und zwei im Süden schmücken den Bau. Am Ostabschluss findet sich die typische Dreifenstergruppe. Bemerkenswert ist, dass zwei der Portale abgestuft sind, eins davon, das auf der Südseite sogar zusätzlich mit Rundstab und Kehle verziert. So etwas findet man bei Feldsteinbauten und dann noch auf dem Land so gut wie nie. Hier kommt ein starkes Repräsentationsbedürfnis zum Ausdruck von Leuten, die sich das auch leisten konnten.
Auf der Südseite hat sich auch noch eins der ursprünglichen Fenster erhalten. Die übrigen wurden barock vergrößert und bekamen einen Korbbogenabschluss. 1720 bekam die Kirche ihren verbretterten Dachturm und vielleicht auch die kräftigen Strebepfeiler im Osten.
Innen ist der Saal flach gedeckt. Auf einer gotischen Altarstipes steht ein Schnitzaltar der Zeit um 1470/80.