1135 ist der Ort als "Nazzegostetin" erstmals genannt. 1403 und 1442 wird ein Burgstall erwähnt. Ab 1442 erwarb das Ehinger Spital nach und nach fast den gesamten Ort. 1532 belehnte Österreich die Stadt Ehingen für das dortige Spital mit der Hoch- und Niedergerichtsbarkeit.
Seit 1805 gehörte Nasgenstadt zum Königreich Württemberg. Möglicherweise deutet bereits die Erwähnung eines Presbyters Markward Mitte des 12. Jahrhunderts auf eine Kirche und eine Pfarrei in Nasgenstadt. Sicher fassbar werden beide 1257. Das Patronat befand sich in den Händen verschiedener Adelsfamilien, bevor es 1482 auf dem Kaufwege in den Besitz des Ehinger Spitals gelangte. 1484 wurde die Pfarrei dem Spital inkorporiert.
Der heutige Bau der St. Peter- und Paul-Kirche wurde 1729, ihr Turm 1749 errichtet. Der Chor dagegen stammt noch aus gotischer Zeit. Die barocke Wendelinkapelle wurde 1696 eingeweiht. Das Dorf ist seit 1971 Stadtteil von Ehingen.