Vähemalt tuhandeaastane ajalooline kauba- ja sõjatee kulges Tartust läbi Võru (Kirumpää) ja Vastseliina ümbruse Pihkvasse. Selle tee ning Tartu piiskopkonna kaitseks rajati Kirumpääle 13. sajandil teetõkkelinnus. Kuna Pihkva vürstiriik püstitas 1330tel aastatel oma kivilinnuse Irboskale, otse vastu Liivimaa alasid, siis tuli ka Liivimaal ehitada oma linnus piirile või selle vahetusse lähedusse.

Linnuse asukohaks valiti kõrge küngas Pihkvasse suunduva muistse kaubatee ääres Piusa jõe kaldal. Nimetatud küngas paiknes vahetult Liivimaa idapiiril ning ta oli kolmest küljest kaitstud veetõketega — künka jalamil suubub Piusa jõkke väike Meeksi oja. Seetõttu oli tegemist ülimalt soodsa asupaigaga.

1342. aastal rajatigi sinna ligikaudu 15x20 meetri suurune ristkülikukujuline mitme meetri paksuste müüridega tornlinnus. Kuna tegemist oli Tartu piiskopkonna alal paikneva uue linnusega, sai ta endale nimeks Neuhausen; Lõuna-Eesti murdesse tõlgituna pärineb sealt ka eestikeelne nimetus Vastseliina. Tornlinnuse esimene korrus kujundati piiskopkonnale omaselt lossikabelina, kuhu paigutati imettegev reliikvia Püha Rist. Paavst Innocentius VI kuulutas 1354. aastal igale Püha Risti sisaldava kabeli külastajale 40-päevase patukustutuse, mistõttu õhtumaise maailma idapiiril asuv Vastseliina lossikabel muutus vägagi külastatavaks palverännupaigaks.

Üsna varsti pärast tornlinnuse rajamist lisati sellele ristkülikukujuline pealinnus, mille ruumid koondati tiibadesse ümber sisehoovi. Ligikaudsete mõõtmetega 40x70 meetrit hõlmas see enamiku künkast. Varasem tornlinnus, mida sellega seoses kõrgendati, jäi pealinnuse läänetiiva keskossa. 1379. aastal oli pealinnus tõenäoliselt juba valminud, sest siis on Vastseliinat nimetatud juba maa tugevaimaks linnuseks.

Hilisematel sajanditel tugevdati ja täiustati linnust veelgi. 15.-16. sajandi vahetuse paiku lisati pealinnuse kirde- ja kagunurkadesse võimsad, ligi 25 meetri kõrgused hoburauakujulised suurtükitornid. Neil tornidel oli rikkalik dekoor kaksikteravkaarsete niððide ning nendes asuvate sõõrpetikute näol. Nimetatud niðid vahelduvad ristikujutistega, mis on ka loomulik, arvestades linnuse kuulumist Tartu piiskopkonnale. Suured müüri laotud ristikujutised näitasid samas igale idast saabuvale rändajale, et ta on jõudnud õhtumaisele ehk lääne-katoliku usuga maale.

Linnuse idaküljele ehitati hiljem veel väike neljatahuline viiekorruseline danskerilaadne torn. Pealinnus ümbritseti ka eeslinnusega, mille madalam müür püstitati künka servale. Eeslinnuse teepoolsesse kagunurka püstitati seejärel veel madal, kolme kaitsekorrusega ümartorn.

Linnuse ehitamine ja täiustamine käis keskajal käsikäes selle purustamisega. Pidi ju iga lõuna poolt Peipsi järve Vene aladelt Eesti aladele tehtud sõjaretk algama Vastseliina linnuse piiramise ja vallutamisega. Ka Liivi sõja üks esimesi avalööke 1558. aastal oli Vastseliina vallutamine. Vene väed jõudsid Vastseliina alla 15. juunil, kuid nende esimene katse linnust vallutada löödi vasturünnakuga tagasi. Seejärel järgnes uus rünnak ja piiramine koos linnuse tulistamise ning mõningase purustamisega, misjärel linnus alistus 1. juulil 1558. aastal.

Venelaste kätte jäi Vastseliina 1582. aastani, mil see loovutati Poolale. Rootsi-Poola sõjas 1620tel aastatel langes Vastseliina aga rootslaste kätte. Kõik nimetatud sõjad purustasid linnust tugevalt. Vene-Rootsi sõjas vallutasid Vastseliina 1656. aastal venelased — rootslased olid vahepeal purustatud piirilinnuse selleks ajaks taas korda teinud. 1661. aastal sõlmitud Kärde rahulepinguga anti linnus rootslastele jälle tagasi.

Põhjalikult ning seekord ka lõplikult purustati linnus 1702. aastal Põhjasõjas. Toona hävis ka linnuse külje all juba keskajal paiknenud väike alev, mis 18. sajandi teisel poolel tekkis hoopis teise paika.

Praeguseks on linnusest järel enamik kahe suure idapoolse suurtükitorni müüridest. Algses kõrguses on alles ka põhjapoolse danskerilaadse torni seinad, samuti üht-teist eeslinnuse lõunapoolsetest müüridest koos ümara nurgatorniga. Ülejäänud linnusest —sh algsest kaitsetornist ja hilisemast pealinnusest — on järel madalad rusuhunnikud. 18.-19. sajandil on neid kasutatud kivimurruna nii Vastseliina mõisa kui ka muude hoonete ehitamiseks.

Linnuse kohal ajaloolise maantee ääres paiknev Piiri kõrts on 19. sajandi algul ehitatud linnusevaremetest pärinevatest tellistest. Keskaegsed tellised olid hilisematest mõõtmetelt palju suuremad. Mainitud kõrts on säilinud ning korrastatud, kuigi ta on kaotanud palju oma algsest välimusest. Nii on kõrtsil kadunud esiküljel paiknenud iseloomulik sammastik.

Linnuse alasid hallanud ning algselt riigi omandis olnud Vastseliina mõis tekkis linnusest edela poole naaberkünkale. Algselt riigi omandis olnud mõis müüdi 1766. aastal Carl von Liphartile. Sellest ajast alates ehitati sinna mitmeid kivihooneid ning rajati liigirikas park. Esinduslikuma lossina ta mõisa peahoonet Vastseliinas siiski välja ei ehitanud, sest 1751. aastal oli ta ostnud juba Tartu-lähedase Raadi mõisa, mida ta kasutas elamiseks. Vastseliinas pandi rõhk seetõttu rohkem majandushoonetele. Enamik Vastseliina mõisahooneid hävis tulekahjus 1926. aastal ning lammutati. Vastseliina mõisa viimane omanik enne 1919. aasta võõrandamist oli Reinhold von Liphart, kes oli Eestimaa üks rikkamaid mõisnikke. Lisaks imekauni toretseva lossina välja ehitatud Raadi mõisale kuulusid talle praktiliselt kõik Vastseliina kihelkonna mõisad.

Kaasaegne Vastseliina asula jääb linnusevaremetest 6 kilomeetri kaugusele läände. 20. sajandi teeõgvenduste tulemusena ei möödu linnusest enam ka tähtsad maanteed - Tartu-Luhamaa maantee kulgeb pea noolsirgena linnusest 3 kilomeetrit edelas. Samuti ei asu Vastseliina linnus enam kaasaegsel piiril. Praegune Eesti-Vene piir kulgeb Liivimaa idapiirist kümnekonna kilomeetri jagu ida pool, hõlmates setude asualasid.

Ajaloolise jaotuse järgi Võrumaale Vastseliina kihelkonda kuulunud mõis jääb kaasajal Võrumaale Vastseliina valla territooriumile.