Según la reorganización división administrativa del año 1998, Pułtusk y su comarca dejaron de pertenecer al voivodato de Ciechanowski De acuerdo a una leyenda existente en la zona el nombre del asentamiento original era el Tusk, pero una gran inundación (ya que está a un nivel muy bajo junto al río Narew) destruyó más o menos la mitad del mismo y el pueblo fue rebautizado por los habitantes, añadiendo "Puł" a Tusk, donde Puł es el prefijo polaco que designa "mitad de".

A menudo los historiadores señalan que la causa más probable es que tomaran el nombre de un pequeño río llamado Pełta, y de ahí "Pułtusk".

Durante la Edad Media se convirtió en un puesto de defensa muy importante contra Lituanos y Prusianos gracias a su castillo.

A partir del siglo XI, Pułtusk albergó el obispado de Płock.

Durante la Polonia Pułtusk tuvo destacamento militar, el regimiento de Infantería número 13.