В отличие от Ивангорода, начало строительства которого известно точно, о времени основания Нарвы среди историков нет общего мнения. Называются даты: 1171, 1221, 1223, 1256, 1276, 1294 годы.
В одних гипотезах Нарва отождествляется с упоминаемым в скандинавских источниках городом Алдейгаборгом, в других связывается с русским Ругодивом. В датской оценочной книге, датируемой 1240 годом, упоминается деревня Нарвиа.
В настоящее время официальной датой рождения города считается 1256 год, когда, как повествует летопись "... придоша Свей и Емь и Сумь и Дидман со своей волостью и множеством рати, и начали чинить город на реке Нарове".