Sejarah Norrtälje berawal pada tahun 1219, saat lokasi itu disebutkan pertama kali sebagai Tälje. Setelah beberapa lama, secara resmi nama itu menjadi Norrtälje untuk membedakannya dari Tälje yang lain di provinsi itu, Södertälje. Lambang kota yang berupa jangkar terbalik diciptakan pada awal 1622 saat piagam dianugerahkan.
Pada tahun 1719 sebagian besar tengah kota yang dibangun dari kayu dibakar oleh para penjarahRusia. Gereja batu yang baru tak diselesaikan hingga 1726, dan 4 tahun sebelumnya balai kota diselesaikan.
