Saksalaiset ja tanskalaiset saivat Liivinmaan - eli suunnilleen nykyisen Viron ja Latvian alueen - valloitetuksi vuoteen 1238 mennessä. Raja-alueilla taistelut kuitenkin jatkuivat venäläisten kanssa, kun Rooman kirkon valtapiiriä pyrittiin ristiretkihengessä ulottamaan myös Peipsijärven itäpuolelle. Tanskalle kuulunutta Pohjois-Viroa suojelemaan ja mahdollisten uusien valloitusten tukikohdaksi rakensivat tanskalaiset Narvajoen rannalle kivilinnan 1250-luvulla. Sotilaallisten näkökohtien ohella linnoituksen paikan valintaan vaikuttivat myös kauppapoliittiset syyt. Narvajokea pitkin kulki vesireitti Itämereltä Pihkovaan ja toisaalta kauppatie Tallinnasta Novgorodiin kulki myös Narvan kautta. Linnoituksen ympärille kehittyikin kauppapaikka, jolle Tanskan kuningas Valdemar IV antoi kaupunkioikeudet 1345. Seuraavana vuonna Tanskan kuningas kuitenkin myi Pohjois-Viron Saksalaiselle ritarikunnalle ja Narvassakin alkoi saksalaisvallan aika.
Saksalaiset vahvistivat Narvan linnoitusta ja rakensivat siihen mm. 50 metriä korkean Pitkän Hermannin tornin, joka korjattuna on nykyäänkin yksi Narvan maamerkeistä. Toisin kuin suuremmissa Liivinmaan kaupungeissa, Narvan 500-800 asukkaasta vain n. 20 % oli saksalaisia, pääosan ollessa virolaisia sekä vatjalaisia. Kaupungin hallinto oli kuitenkin saksalaisten käsissä.
Moskovan suuriruhtinaskunta vahvistui ja laajeni 1400-luvulla ja kun se sai alistettua Novgorodin valtaansa 1478, alkoi Liivinmaakin olla vaaravyöhykkeessä. Moskovan suuriruhtinaan Iivana III:n käskystä rakennettiin 1492 Narvajoen itärannalle linnoitus, joka sai nimekseen Iivananlinna (Ivangorod). Saksalainen ritarikunta sai kuitenkin merkittävän voiton venäläisistä 1502, jonka ansiosta Liivinmaa sai nauttia yli 50 vuotta kestäneestä rauhanajasta. Kun rauha päättyi 1558, Narva rajalinnoituksena oli venäläisten ensimmäisen hyökkäyksen kohteena. Kaupunkia piiritettiin tammikuusta toukokuuhun, jolloin se tulipalojen pahoin runtelemana joutui antautumaan. Narvasta tuli Venäjälle tärkeä ulkomaankauppakaupunki ja sinne muutti venäläisten kauppiaiden lisäksi myös paljon virolaisia ja vatjalaisia käsityöläisammattien harjoittajia.
Vuonna 1581 ruotsalaiset valloittivat Narvan ja kaupunki perustettiin tavallaan uudelleen. Tanskalaisajalta peräisin oleva Lyypekin kaupunkilaki kumottiin ja Narvassa saatettiin voimaan ruotsalainen kaupunkilaki. Kaupunki liitettiin Inkerin ja Käkisalmen lääniin, eikä se siten enää kuulunut hallinnollisesti Viron kuvernöörin alaisuuteen. Muualla Liivinmaallahan säilyivät vanhat lait koko Ruotsin vallan ajan. Venäläisten lähdettyä Narvasta kaupunkiin muutti uusia asukkaita paitsi Virosta, myös Suomesta ja Ruotsista. Lisäksi Narvaan sijoitetun varuskunnan joukot koottiin lähes kokonaisuudessaan Suomesta.
Ruotsin vallan aika kesti Narvassa toistasataa vuotta. Kun Ruotsi sai haltuunsa 1617 myös Inkerinmaan, Narva ei ollut enää rajalinnoitus. Idänkauppa toi kaupunkiin vaurautta varsinkin 1600-luvun lopulla. Tämä näkyi myös kaupungin kasvuna: siitä tuli Riian ja Tallinnan jälkeen Liivinmaan kolmanneksi suurin kaupunki ja sen asukasluku ylitti 3000 rajan. Vuoden 1659 tulipalon jälkeen rakennettiin yhteinäiseen barokkityyliin koko kaupungin keskusta, joka 1900-luvulla oli kaupungin matkailuvaltti toiseen maailmansotaan asti. Ruotsalaiset myös linnoittivat Narvaa ja sen ympärille rakennettiin uuden puolustustekniikan mukainen bastionivyö. Linnoituslaitteet olivatkin tarpeen, kun suuren Pohjan sodan sytyttyä Pietari Suuri ryhtyi joukkoineen piirittämään kaupunkia. Sillä kertaa Narva jäi valloittamatta, kun Kaarle XII tuli apuun ja löi marraskuussa 1700 piirittävät venäläisjoukot. Neljä vuotta myöhemmin venäläisten uusi piiritys kuitenkin johti kaupungin antautumiseen, jonka jälkeen asukkaat vietiin vankeina kauas sisä-Venäjälle.
Pietari Suuri säilytti pääpiirteissään Liivinmaalla Ruotsin vallan aikaiset hallinnolliset rajat, ja tämän vuoksi Narvakin kuului aina Viron itsenäistymiseen asti Pietarin kuvernementtiin. Suuren Pohjan sodan jälkeen kaupungin merkitys ulkomaankaupassa väheni ja väkiluku pieneni. Hiljaiselo päättyi vasta 1800-luvun puolivälissä, jolloin Narvaan Kreenholmin saarelle perustettiin suuri tekstiilitehdas. Tehdas kasvoi alansa suurimmaksi Euroopassa ja 1910-luvulla siellä työskenteli jo yli 10 000 ihmistä. Itse Narvan kaupungissa oli tuolloin n. 21 000 asukasta. Taloudellista toimeliaisuutta lisäsi 1870 rakennettu Tallinna–Pietari-rautatie, joka kulki Narvan kautta. Rautatie toi myös varakkaita lomanviettäjiä Narvan seudulle ja näiden tarpeita palvelemaan perustettiin Narva-Jõesuuhun kylpylä 1870-luvulla. Vaikka sen ympälle syntynyt huvilayhdyskunta on pääosin hävinnyt, yksittäisiä vanhoja huviloita voi vieläkin löytää Narva-Jõesuusta.
Ensimmäisen maailmansodan lopulla Narva oli puolisen vuotta Saksan keisarillisen armeijan miehittämä ja saksalaisten joukkojen vetäydyttyä Virosta miehitti puna-armeija Narvan marraskuussa 1918. Kaupungissa perustettiin Virolle bolševikkihallitus, joka ilmoitti puna-armeijan tulleen maahan antamaan apua Viron työläisille. Jaan Anveltin johtama hallitus joutui kuitenkin pian poistumaan Narvasta, kun suomalais-virolaiset joukot valloittivat kaupungin tammikuussa 1919. Vaikka Narva pysyikin koko Viron vapaussodan ajan virolaisten käsissä, se kärsi pahoja vaurioita venäläisten tykkitulesta. Vapaussodan kovimmat taistelut käytiinkin Narvajoen linjalla loppuvuodesta 1919. Kaupungin kärsimyksiä lisäsivät sodan mukana kaupunkiin levinneet taudit, ennen muuta lavantauti, johon menehtyi lähes 2000 narvalaista.
Ensimmäisen maailmansodan jälkeen Narvan teollisuustuotanto väheni verrattuna sotaa edeltävään aikaan lähinnä siksi, että Viron itsenäistyttyä vienti Venäjälle lähes tyrehtyi. Jossain määrin tätä korvasi kasvava matkailuelinkeino, mutta siitä huolimatta Narvan asukasluku väheni sotienvälisenä aikana yli neljällä tuhannella. Toisen maailmansodan aikana, etenkin vuoden 1944 pommituksissa, vaurioitui 98 % kaupungin rakennuskannasta ja sodan jalkoihin jäänyt kaupunki käytännössä tyhjeni asukkaista. Neuvostoaikana kaupunki sai uudet asukkaat (yli 80 000 v. 1990) sekä rakennukset, mutta kovin erinäköiset kuin ennen. Nykyiset asukkaat ovat Neuvostoliiton peruja: ennen vuotta 1940 kaupungin asukaista lähes 70 % oli virolaisia, vuonna 1990 vain 4 %. Vanhoista rakennuksista kunnostettiin sodan jälkeen vain muutamia ja Narvan kaupunkikuvaa hallitsee nykyisin barokin sijasta neuvostoarkkitehtuuri. Turistinähtävyyksien joukosta on kadonnut myös Narvajoen mahtava koski, joka 1950-luvulla valjastettiin sähköntuotantoon.
Tuskin mitään muuta virolaista kaupunkia ovat historian käänteet muokanneet yhtä kovalla kädellä kuin Narvaa. Kaupunki on kuitenkin, kaikista muutoksista huolimatta, pysynyt nimikkojokensa rannalla nyt tasan 660 vuotta. Tämän pohjalta voisi veikata, että siellä se sinnittelee tulevaisuudessakin ja todennäköisesti ilmeeltään muuttuneena.