Veltin stammte aus dem Basler Rittergeschlecht der Neuenstein. Ab 1483 war er Bürger von Solothurn. Geboren um 1453. Gestorben 1491 in Solothurn. Sohn des Rudolf von Neuenstein.

In den Jahren 1461-1464 war N. unter Fürstbischof Johann von Venningen  erster Vogt der Herrschaft Zwingen und wohnte auf Schloss Zwingen. Um 1465 wird er als Vogt auf dem von Solothurn besetzten Schloss Angenstein erwähnt. Sein Verhalten in dieser Stellung veranlasste die Stadt Basel zur Forderung an Solothurn, die Strassen vor seinen Übergriffen zu schützen. Unter anderem war N. in die Grafschaft Montbéliard eingedrungen, hatte Dörfer geplündert, Gefangene gemacht und auf Angenstein abgeführt. Als Solothurn die Feste Angenstein wieder verlor, zog er nach Wahlen auf den alten Familiensitz Schloss Neuenstein, den er von der Familie Bärenfels zurückkaufen konnte.

Im Mai 1473 trat N. in den Sold der Stadt Basel und verpflichtete sich im September gleichen Jahres durch einen Vertrag, mit drei Pferden und zwei Knechten Dienst zu tun. Im ersten Dienstjahr begleitete er die vereinigten Berner und Solothurner als Beobachter nach Montbéliard. Im November gleichen Jahres kämpfte er für die mit den Eidgenossen und den Österreichern verbündete Niedere Vereinigung (Reichsstädte Strassburg, Basel, Colmar und Schlettstadt) in der Schlacht von Héricourt. Kurz danach erhielt er den Auftrag, die vom Herzog von Burgund belagerte Stadt Neuss zu entsetzen. Er besetzte als Feldhauptmann mit mehreren Hundert Mann einen Posten am anderen Flussufer und schlug reiche Beute auf Kosten der Burgunder. 1475 wurde er nochmals mit 100 Mann zur Unterstützung nach Neuss berufen. Der Herzog hatte sich aber inzwischen zurückgezogen. Trotzdem plünderten die Basler in der Gegend um Neuss und N. kehrte mit reicher Beute auf seine Burg zurück.
1476 befand sich N. mit einer stadtbaslerischen diplomatischen Mission beim Herzog Sigismund von Österreich in Innsbruck und verpasste so die Schlacht bei Grandson.
Als im Juni desselben Jahres Burgund Murten belagerte, zog er unter dem Oberbefehl des Basler Altbürgermeisters Peter Roth dorthin. Er kommandierte zusammen mit Oberzunftmeister Iselin die «Reisigen». Am Morgen des 22. Juni (Zehntausendrittertag) kundschaftete er zusammen mit anderen kriegserfahrenen Leuten die Lage aus.
Als die Basler nach gewonnener Schlacht heimkehrten, blieb N. als Befehlshaber eines kleinen Fusstrupps mit den Eidgenossen zurück und zog gegen Savoyen. In Lausanne soll er erneut reiche Beute geschlagen haben.
Am 1. September 1476 stand N. wiederum im Sold Basels mit 10 Reitern und 160 Fussknechten im Heerlager von Herzog Renatus von Lothringen, dessen Stadt Nancy vom Herzog von Burgund belagert wurde. In der Schlacht bei Nancy vom 5. Januar 1477, in der Karl der Kühne von Burgund sein Leben verlor, beteiligte sich N. direkt und zeichnete sich aus. Er erhielt anschliessend nebst reicher Beute zusammen mit weiteren drei Baslern von Herzog Renatus den Ritterschlag als Dank für seine Tapferkeit.
Am 20. Mai 1477 löste er sein Dienstverhältnis mit der Stadt Basel auf.

1483 erneuerte N. das bereits von seinem Vater erworbene Burgrecht mit Solothurn. Bald darauf kam es zu Spannungen mit dem Bischof von Basel, Kaspar zu Rhein. N. hatte einen seiner Nachfolger im Amt des Vogts von Zwingen, Hans Heinrich Ullin von Delsberg, auf offener Strasse entführt und in Pfeffingen gefangen gesetzt. Der Bischof wandte sich an die eidgenössischen Orte, die in den Beziehungen zwischen Solothurn und Fürstbistum vermittelten. Die Fehde des N. mit dem Bischof wurde offiziell eingestellt, doch der Gefangene blieb noch lange auf Burg Pfeffingen sitzen und die Feindseligkeiten zwischen den Parteien setzten sich in der sog. Kappeler Fehde fort. Zusammen mit den Gebrüdern Kappeler von Zwingen und den Brüdern Ludi aus Wahlen überfiel N. Dörfer, raubte, plünderte, brandschatzte, mordete und gewährte den Übeltätern Schutz auf seiner Burg Neuenstein. 1490 ermordete die Bande den Vogt von Zwingen, später verwüstete und plünderte sie das Schloss Zwingen. Die eidgenössische Tagsatzung musste sich mehrmals mit der Angelegenheit befassen und erlaubte dem Bischof schliesslich, die gewalttätige Bande auch auf eidgenössischem Gebiet zu verfolgen. Einige der Bandenmitglieder wurden 1492 gefasst und in Zwingen hingerichtet. N. entging dieser Schmach durch seinen früheren Tod 1491 in Solothurn.