Brunstorf wird erstmals am 13. Januar 1371 urkundlich erwähnt: In einer Verpfändungsurkunde von Herzog Albrecht von Mecklenburg an den Bischof von Schwerin werden neben „Guthendorpe“ (Alt Guthendorf) und „Nigen Guthendorpe“ (Neu Guthendorf) auch die „Städte und Schlösser Marlow und Sülze“ sowie „Brunestorpe“ genannt.
1731 wurde Brunstorf von Marlow nach Kölzow umgepfarrt. Eine Karte aus dem Jahr 1764 zeigt, dass Brunstorf damals ein völlig anderes Erscheinungsbild hatte als heute: Das Dorf war als klassisches Runddorf angelegt – die einzelnen Gehöfte gruppierten sich kreisförmig um einen zentralen Dorfteich. Aus dieser Darstellung lässt sich schließen, dass Brunstorf zu diesem Zeitpunkt noch kein Gutsdorf war.
Im Jahr 1929 verkaufte der damalige Gutsbesitzer, Rittmeister Charly Mehns, seine Güter Wöpkendorf, Kanneberg und Brunstorf an die „Kultur- und Siedlergesellschaft deutscher Landwirte“ – ein Schritt, der durch die angespannte wirtschaftliche Lage in der Landwirtschaft bedingt war. Nach anfänglichen Schwierigkeiten wurden die Güter aufgesiedelt, überwiegend an Siedler aus dem Badischen und Westfälischen, die zu rund 90 % katholischen Glaubens waren.
Bereits 1895 war mit dem Bau der Eisenbahnstrecke Sanitz–Tribsees auch ein Netz von Feldbahnen entstanden. Eine dieser Strecken führte von Alt Guthendorf über Brunstorf und Wöpkendorf bis zum Bahnhof Dettmannsdorf–Kölzow. Die Stadt Marlow erwog mehrfach, diese Feldbahn bis in die Stadt zu verlängern und sie mit einem kleinen Personenzug zu betreiben – ein Vorhaben, das jedoch nie umgesetzt wurde.
Zu DDR-Zeiten war in der Nähe von Brunstorf die Errichtung einer militärischen Anlage geplant. In diesem Zusammenhang gab es Überlegungen, den Ort „leerzusiedeln“. Nach der politischen Wende wurde der Standort zur Marinefunksendestelle der Bundeswehr. In diesem Zuge wurde die Zufahrtsstraße asphaltiert, und es entstanden neue Wohnhäuser in landschaftlich reizvoller Umgebung.
