Bereits 946 wird Brenz als „Terra Brenzia“ erstmals in einem Stiftungsbrief Otto I. erwähnt. Im Jahre 1230 erfolgt die urkundliche Ersterwähnung durch Verhandlungen zwischen den Fürsten Johann und Pribislav von Mecklenburg und Bischof Brunward von Schwerin. Damals gehörte das Land Brenz, aus dem die Vogtei Neustadt hervorgegangen ist, zur Schweriner Diöcese. 

Brenz, ein deutsches Bauerndorf, in der ersten Urkunde 1361 erwähnt, besteht wahrscheinlich schon seit dem XII. Jahrhundert und war in alten Zeiten Hauptort eines eigenen Landes, aus dem das Amt Neustadt entstand. Ein kleines Gewässer durchfließt die Gemeinde zur Müritz-Elde-Wasserstraße. Im Norden des Ortes ist ein bemerkenswerter, fast kreisrunder Wall mit einem Durchmesser von 75 m. Es finden sich auch Spuren dieses Burgwalls, der noch heute diesen Namen führt. Vielleicht ist dies die alte Hauptburg der wendischen terra Brenitz.