Нарымский острог был построен среди необозримых западносибирских болот на берегу Оби, близ впадения в неё реки Кеть. И название своё получил от селькупского няр – болото. Точное время закладки острога, имена его основателей и место, где он был построен неизвестны. Но скорее всего, острог был поставлен во время русского похода 1597 года на князя Пегой Орды Воню, отказавшегося платить ясак русскому царю и заключившего союз с Кучумом. В результате похода Воня был разгромлен, его Нарымский городок взят. А на его месте или где-то неподалёку русские построили свой острог – опорный пункт русской власти в Нарымском крае. В остроге имелся небольшой гарнизон в несколько десятков служилых людей – годовальщиков, посылаемых из Сургута, которые собирали ясак с местного населения.
Царский наказ предписывал воеводам, посланным на князя Воню, построить острог лишь как временное укрепление, пока не покорят область под царскую руку, а затем его разорить. «Потому что место дальнее, запасы возить туда тяжело, а малым людям в остроге, в Пегой Орде быть нельзя, оттого что у князя Вони с братией и детьми собирается до 400 человек». Однако, победа над Пегой Ордой оказалась, видимо, столь решительной, что планы изменились.
В 1601 году Нарымский острог получил статус города. Тогда же был создан Нарымский уезд. Из-за низменного местоположения острог постоянно подтапливался водами Оби. Воевода Мирон Хлопов в 1611 году писал в Тобольск: «Отмывает отрог водою сажени по четырех и по пяти, а от берега отодвинуться негде, пришел мох и болота». Острог неоднократно переносили на новое место, в 1613 и 1619 годах, когда он полностью сгорел. Но в 1630 году острог снова затопило: «Пришла вода великая, больши прежних вод, и острог во многих местах выломало и разносило, и башни сметало». На нынешнее своё место, на берегу Безымянной протоки Оби, Нарым перенесён в 1632 году. Первоначальное место Нарымского острога ныне точно неизвестно.
Население города росло очень медленно, в середине 17 века оно составляло не более 100 человек. Местное население за пределами города составляли селькупы. Сын Вони Тайбохта и его тесть Вагай Кичеев приняли присягу русскому царю, а с 1610 года официально поступили на службу. Они получали жалование мукой, солью, крупой, толокном и деньгами.
Первоначально острог планировался как временный опорный пункт, основным его укреплением был частокол. Затем планы изменились, острог стал постоянным поселением, центром уезда с воеводским правлением. В остроге были возведены все необходимые строения. Планировка острога и построек типичны для сибирских городов. На его территории находились жилые избы, воеводский дом, приказная изба и деревянная церковь во имя Спаса Всемилостивого. Жилые избы стояли не только в остроге, но и на посаде. Башни – как проездные, так и сторожевые по углам - были четырехугольными в плане. Проездные делались выше и их венчали смотровые вышки. Все башни завершались четырехскатными тесовыми крышами. К исходу 17 века Нарым утратил своё военное значение, прекратила своё существование и его крепость. Город оставался административным и торговым центром обширного, но малонаселённого края.