Am 28. August 1362 wird Neustadt als Keresztyenfalu zum ersten Mal urkundlich erwähnt: in einem Privilegium König Ludwigs des Großen für den hervorragenden Neustädter Pfarrer Nikolaus und seinen Bruder Rudolf, in dem ihnen der König in Anerkennung ihrer Verdienste die Einkünfte der Neustädter Mühle, Befreiung von allen Abgaben sowie die Verleihung adliger Vorrechte zusichert.
In der Folgezeit tauchen in verschiedenen Dokumenten noch weitere Namensformen auf, z.B.: 1367 „Villa Cristiani”, 1377 zum ersten Mal die vermutliche Fehlübersetzung aus dem Deutschen „Nova Civitas”; außerdem noch „Neostadium”, „Neapolis”, „Nayer-”, „Neyer-”, „Newer-” / „Newr-” oder „Newstatt” und schließlich „Neustadt”.
Manche Historiker gingen davon aus, dass der deutsche Name (im Sinne von „die neue Statt / Stätte”) auf eine durch Innerkolonisation entstandene Zweitgründung, d. h. eine von einem anderen Ort aus vorgenommene Neugründung deutete. Dem steht entgegen, dass die benachbarten Ortschaften zu dem angenommenen Zeitpunkt wohl kaum so stark waren, eine Tochtergemeinde zu begründen. Es ist vielmehr anzunehmen, dass das mittelalterliche Neustadt um die gleiche Zeit entstand wie die Nachbargemeinden.
Wenn man zudem das imposante romanische Westportal der evangelischen Kirche samt dem Rosenfenster darüber betrachtet und bedenkt, dass sie Überreste der alten Nikolauskirche sind, die auf das Jahr 1270 zurückgeht, fällt es schwer zu glauben, dass eine neu gegründete Siedlung in den ersten Generationen bereits zu einer solchen Bauleistung fähig gewesen sein soll.
Die rumänische wie die ungarische Namensform (Christiansdorf) lassen sich anscheinend auf den Personennamen Christian zurückführen. Der Name Christian bzw. eine (rechtliche) Beziehung zu dem gleichnamigen Ort begründen wohl auch die rumänische Bezeichnung der Schulerspitze, Cristianul Mare.
Die Gründung des Ortes geschah vermutlich um das Jahr 1220 durch etwa zehn Kolonistenfamilien.