Die Anfänge Horstmars liegen im frühen Mittelalter. Damals wanderten in den dünn besiedelten hiesigen Raum Menschen aus vielen, vor allem norddeutschen Regionen ein. Sie siedelten auf waldfreien Flächen, wo Wasser für die Versorgung von Mensch und Vieh vorhanden war, was durch Quellen am Südrand des Schöppinger Berges, u. a. des Immelbachs und der Wirlocks gegeben ist. Den angrenzenden Wald nutzten sie als „Weide“ für ihre Rinder und Schweine, rodeten aber meist auch einen Teil davon zur Vergrößerung der Ackerflächen. Die ältesten Siedlungen wiesen noch wegen des genutzten kreuz und quer Furchen ziehenden Hakenpfluges Block-Fluren auf, in denen sie ihre Höfe errichteten. Mit der Erfindung und Verbreitung des mit Rädern versehenen Scharpfluges, der die Schollen in Streifen umbricht und deshalb längere Saatbeete erfordert, erhielten die Ackerflächen ab etwa dem 9. Jahrhundert eine ei- oder schildförmige Form. Zudem wurden die Höfe an den Rand verlegt. Die meisten dieser Ackerflächen haben heute noch die Flurbezeichnung „Esch“, so z. B. der Stadtesch und der Lütken Esch. „Esch" ist ein altgermanisches Wort für „Ackerland“ oder „Saatfeld“; als Flur handelt es sich meist um Flächen, die quer in schmale, langgestreckte Ackerbeete aufgeteilt sind.

Im Rahmen der mit der Unterwerfung verbundenen Christianisierung der Westfalen wurden entlang der Heerstraße vom Niederrhein an die Ems im hiesigen Raum die Taufkirchen Schöppingen, Wettringen und Rheine gegründet. Der Bereich Horstmar mit den Bauerschaften Niedern und Schagern und der des Dorfes Leer mit den Bauerschaften Haltern und Ostendorf wurden der Taufkirche Schöppingen zugeordnet, wo an bzw. über einer kräftig sprudelnden Quelle eine Kirche errichtet wurde. Ludwig der Fromme, Nachfolger Kaiser Karls des Großen, schenkte 838 diese drei Taufkirchen mit ihren „Einkünften“ dem Damenstift Herford. Unter Fürstbischof Hermann II. (1173 – 1203) wurden Horstmar und Leer selbständige Pfarren, also von Schöppingen abgepfarrt, nachdem auch hier Kirchen gebaut worden waren.

Wann der an der Heerstraße vom Niederrhein nach Rheine an der Ems u. a. auf dem Hagen am Pass von Horstmar oberhalb großer, vom Immelbach durchflossener Teiche eine Burg ausgebaut wurde, ist bis heute ungeklärt. Die hier ursprünglich ansässigen Edlen von Horstmar sind 1154 erstmals urkundlich mit Namen „von Horstmar“ erwähnt; lassen sich aber schon seit 1092 annehmen, noch ohne Zusatz „Horstmar“. Zu ihrer „Herrschaft“ gehörten Bauernhöfe und andere landwirtschaftliche Nutzungsrechte in der Umgebung von Horstmar und Recke, wo die Horstmarer eine Eigenkirche besaßen, sowie Ibbenbüren. Letztere schenkten sie 1189 dem Bischof von Osnabrück zur Gründung eines Klosters, was aber nicht erfolgte.