Нейгаузен был основан в 1273-м году Дерптским епископом на границе его владений и Псковского княжества. Городок был посвящён Деве Марии, получив в её честь своё первое название — Фрауенбург (Город Госпожи). Позже, однако, прижилось название Neuhausen (Новое строение), напоминающее о том, что крепость была выстроена на месте более древнего чудского городища. Отсюда же методом кальки возникли его русское – Новгородок и эстонское — Vastseliina названия.
В 1354-м году рижский архиепископ в своём письме папе Иннокентию VI описал чудо, случившееся в часовне Нейгаузена ночью в сентябре 1353-го года, когда люди, услышав музыку в часовне, пошли посмотреть на то, что происходит, то увидели две свечи в таинственной молнии. Крест, что обычно висел на стене, теперь стоял загадочно без любой поддержки на алтаре. После этого чудо стали приходить осматривать люди из Ливонии и даже из самой Германии. Много слепых людей прозрели и те, кто не слышал хорошо прежде, стали слышать снова. Крест находился в замковой часовне. Посещение часовни давало 40-дневное отпущение грехов, что было продекларировано папой Иннокентием VI.
В 1342-м году в Нейгаузене было завершено строительство замка, начатое по приказу магистра Ливонского ордена Бурхарда фон Дрейлебена. Имея 19-метровые башни и стены 4-метровой толщины, Нейгаузен стал как форпостом католической экспансии Ордена на восток так и серьёзным оборонительным узлом на пути ответных походов русичей.
Таким образом, неудивительно, что вскоре после начала Ливонской войны и взятия воеводами Адашевым, Басмановым и Бутурлиным в мае 1558-го года Нарвы (русский Ругодив) 60-тысячная русская армия на своём пути вглубь Ливонии 15-го июня приступила к осаде Нейгаузена.
Крепость защищали 60 рыцарей с несколькими сотнями воинов во главе с Юргеном Юксюллем. Несмотря на свою малочисленность, они почти месяц стойко сопротивлялись, отражая натиск русских войск под командованием воеводы Петра Шуйского и князя Андрея Курбского. После разрушения русской артиллерией крепостных стен и башен немцы 30-го июня отошли в верхний замок. Оставшиеся в живых орденцы приняли решение прекратить бессмысленное сопротивление и сдали крепость. По заверению штатного ливонского хроникёра, Юксюлль сотоварищи были раздеты догола и отпущены, местные чудские крестьяне, укрывшиеся в замке, зверски убиты, а младенцы, естественно, разрублены пополам.
С тех пор до 1582-го года Новгородок-Нейгаузен принадлежал русским, потом перешёл к полякам, затем к шведам. В 1655-м году полуразрушенные укрепления Нейгаузена были восстановлены шведским королём Карлом X, однако уже в следующем веке Нейгаузен потеряет своё значение как крепость. В 1656-м году русские вновь овладели им, но уже в 1661-м году опять уступили его шведам.
Ныне живописными развалинами крепости Новгородка-Нейгаузена можно полюбоваться в 3-х верстах к востоку от посёлка Вастселийна Выруского уезда. В комплекс открытого здесь музея входит также большой парк, окружающий замковый холм.
В книге русского писателя И.И. Лажечникова «Последний Новик», написанной в 1833-м году, имеется прекрасное художественное описание Новгородка-Нейгаузена:
«В Нейгаузенской долине, где пятами своими упираются горы Ливонские и Псковские, проведена, кажется, самою природою граница между этими странами. Новый-Городок (Нейгаузен) есть уже страж древней России: так думали и князья русские, утверждаясь на этом месте. Отважные наездники в поле, они были нередко политики дальновидные, сами не зная того.
Замок нейгаузенский построен на крутом берегу речки Лелии, передом к Лифляндии. Четыре башни по углам, соединяющая их ограда, — все это грубо выведенное из дикого, неотесанного камня, — довольно глубокий овраг с трех сторон, с четвертой — обделанный берег, — вот вся искусственная сила этой твердыни. Зато как далеко, как зорко оглядывает она перед собою вправо и влево всю немецкую сторону! Все, что идет и едет от Мариенбурга, Риги и Дерпта, все движения, за несколько десятков верст, не укроются от сторожкого ее внимания. Только сзади господствует над нею отлогое возвышение, беспрестанно поднимающееся на две с лишком версты до гребня горы Кувшиновой; но там — сторона русская! Речка Лелия течет перед лицом замка, изгибаясь, в недальнем расстоянии, с левой стороны назад, с правой вперед. На углу правого изгиба насыпь (вероятно, и на левом была подобная же, но она застроена теперь корчмою); несколько таких искусственных высот, служивших русским военными укреплениями, идут лестницею по протяжению печорской дороги. Некоторые из них уцелели доныне, иные обросли рощицами, другие изрыты дождями, а может быть, и жадностью человеческою. Струи речки мелки, но шумят, строптивые, будучи преграждены множеством камней, временем брошенных в нее с высоты башен.
Вид из замка обнимает Лифляндию на несколько десятков верст; перед глазами разостлан по трем уездам край ее одежды. Прямо за речкою, в средине разостлавшейся широко долины, встал продолговатый холм с рощею, как островок; несколько правее, за семь верст, показывается вполовину из-за горы нейгаузенская кирка, отдаленная от русского края и ужасов войны, посещавших некогда замок; далее видны сизые, неровные возвышения к Оденпе, мызы и кирки. Левее струится из мрачной дали прямо на Нейгаузен дорога рижская; еще левее чернеет цепь гор Гангофских, между которыми поднимает обнаженное чело свое царь этих мест — Муннамегги (Яйцо-гора), наблюдающий, на протяжении с лишком ста верст, рубеж России от Мариенбурга через Печоры до Чудского озера, и накрест свою область от Нейгаузена, через возвышения Оденпе и Сагница, до вершины Гуммельсгофской. Между горами видна и знакомая нам оппекаленская кирка. Все как на блюде! Русская, однакож, сторона закрыта отсюда скатом Кувшиновой горы, как полою великолепного шатра. Чем далее поднимаешься по этому скату, тем картина расширяется и углубляется. Глаз без помощи орудия отказывается схватить все, что она предлагает ему. На вершине Кувшиновой горы сильнее бьется сердце русского: с нее видишь сияние креста и темные башни печерского монастыря, место истока Славянских Ключей, родины Ольги, Изборск, и синюю площадь озера Псковского. Здесь уже настоящая Русь! Только полуверцы, обычаями, верою, языком — смесь лифляндцев с русскими — означают переход из одного края в другой.
Во время, которое описываем, замок представлял, как и ныне, одни развалины. Взорван ли он и покинут без боя шведами, бессильными удержать его с малым стреженем, который он мог только в себе вмещать, от нападений русских, господствовавших над ними своими полевыми укреплениями, давним правом собственности и чувством силы на родной земле; разрушен ли замок в осаде русскими, — история нигде об этом не упоминает. Известно только, что последние в 1072 г. уже были властители Нейгаузена. Здесь и у стен печерского монастыря было сборное место русских войск, главное становище, или, говоря языком нашего века, главная квартира военачальника Шереметева; отсюда, укрепленные силами, делали они свои беглые нападения на Лифляндию; сюда, не смея еще в ней утвердиться, возвращались с победами, хотя еще без славы, с добычею без завоеваний, с чувством уже собственной силы, но не искусства. Здесь полководцы, обезопасенные упрямою беспечностью Карла, имели время обдумывать свои ошибки, готовить новые предначертания и учиться, таким образом, науке войны…».