The earliest roots of the association go back to the founding of the football club Neustrelitzer Fußball Club which soon grew into a more general sports club known as Neustrelitzer Sportverein. The sports club failed after 1919, but the football department immediately re-established themselves as Ballspielverein Neustrelitz. A second local football club known as SV Viktoria Neustrelitz was formed in 1925 and was joined by BV the following year. Viktoria in turn merged with SG Corso Neustrelitz in 1931 to form SG Corso Viktoria Neustrelitz which played through to the end of World War II when occupying Allied authorities ordered all organizations in the country, including sports and football associations, disbanded.
A successor was created in 1946 as SG Neustrelitz, and as was common in East Germany at the time, would undergo several name changes playing variously as BSG Konsum Neustrelitz (1949), BSG Empor Süd Neustrelitz (1951), BSG Motor Neustrelitz (1952), and BSG Maschinelles Rechnen Neustrelitz (1971). The club took on its current name in 1975 after being disassociated from its industrial sponsor.
The club made several ascents to the second division DDR-Liga, but was never able to firmly establish itself at that level of play. In 1963 it appeared that BSG had won its way through a playoff round to the DDR-Liga, but found itself disqualified over the use of an ineligible player. After being promoted in 1964 Neutrelitz would play its way to the 1/8 final of the East German Cup despite a last place finish in regular league competition. The team lost a close contest there by a score of 1:2 to FC Carl Zeiss Jena.
After German re-unification in 1990 TSG played in the Landesliga Mecklenburg-Vorpommern (VI) winning promotion to the Verbandsliga Mecklenburg-Vorpommern in 1996. They immediately claimed the title there, again winning promotion, this time to the NOFV-Oberliga Nord (IV). They struggled through three seasons at that level and after a 16th place finish were demoted to the Verbandliga where they spent two years. Neutrelitz re-claimed a place in the Oberliga in 2002. Ten years later Neustrelitz reached the re-formed Regionalliga Nordost, which they won in 2014, but missed promotion to the 3. Liga after a defeat to FSV Mainz 05 II in the playoff.