Новый этап развития города, который в конце III или начале IV века получил название Париж (то есть город паризиев), наступил в конце X – начале XI века. В это время начинают формироваться поселения на правом берегу Сены: на холмах Святого Гервасия (Сен-Жерве) и Святого Медерика (Сен-Мерри), а также на месте будущей Ратушной площади. Интересы безопасности требовали окружить заселенную местность крепостной стеной. Она была возведена при короле Филиппе II Августе: в 1190–1208 годах на правом берегу, в 1209–1213 годах – на левом (правда, есть предположение, что в конце X или начале XII века Париж окружала еще одна стена, однако поскольку никаких ее остатков обнаружить не удалось, существование ее остается сугубо гипотетическим). Общая длина новой стены составляла около 5400 метров, ширина у основания равнялась в среднем 3 метрам, высота доходила до 10 метров. Филипп II Август был настолько уверен в прочности возведенных в его царствование укреплений, что не счел нужным окружить их рвами. В крепостной стене были проделаны ворота (каждые под защитой двух башен); об их числе и местоположении историки судят предположительно. На правом берегу ворота Святого Антония располагались, по-видимому, на месте современного дома 101 по улице Святого Антония (Сент-Антуанской), ворота Святого Мартина – на месте нынешнего дома 200 по улице Святого Мартина (Сен-Мартен), ворота Святого Дионисия – на месте нынешнего дома 135 по улице Святого Дионисия (Сен-Дени), Монмартрские ворота – на месте нынешнего дома 30 по Монмартрской улице, ворота Святого Гонория – на месте нынешнего дома 148 по улице Святого Гонория (Сент-Оноре). На левом берегу Нельские ворота располагались на месте, где сейчас стоит здание Французского института, ворота Бюси стояли на месте нынешнего Торгового двора Святого Андрея, ворота Святого Германа – на пересечении нынешней улицы Медицинской Школы и Сен-Жерменского бульвара, ворота Святого Михаила – на пересечении нынешней улицы Господина Принца и бульвара Сен-Мишель, ворота Святого Иакова – на месте нынешнего дома 172 по улице Святого Иакова (Сен-Жак), ворота Святого Марселя – на месте домов 47–50 на нынешней улице Декарта, а ворота Святого Виктора – на месте нынешнего дома 2 по улице Школ. Впоследствии число ворот увеличилось. Площадь земли, окруженной этой крепостной стеной, составляла 2,53 км²; далеко не вся эта территория была застроена; бóльшая часть ее была занята полями и виноградниками. Вне крепостной стены Филиппа II Августа на правом берегу Сены располагался замок Лувр, окруженный собственными укреплениями и рвом и таким образом защищенный от возможных нападений. К концу XIII века в Париже, согласно написанному около 1300 года «Сказанию о парижских улицах» поэта Гийо, насчитывалось 310 улиц: 36 на острове Сите, 80 на левом берегу и 194 на правом.

Город строился не только внутри крепостных стен, но и вне их; поэтому возникла необходимость расширить территорию, защищенную укреплениями. Следующая крепостная стена вокруг Парижа была построена спустя полтора столетия, в 1356–1383 годах. Начал ее строительство купеческий старшина Этьен Марсель, который реально правил городом после того, как король Иоанн II в сражении при Пуатье попал в плен к англичанам. Строительство продолжилось при короле Карле V, и стену принято называть его именем. На левом берегу эта стена практически повторяла предыдущую; работы состояли лишь в укреплении и обновлении старой крепостной стены Филиппа II Августа. На правом же берегу была построена новая стена общей длиной 4900 метров с шестью новыми воротами: ворота Святого Антония располагались на месте современной улицы Бастилии, ворота Тампля – там, где сегодня пересекаются улицы Тампля и Мелé, ворота Святого Мартина – там, где пересекаются нынешние улицы Святого Мартина (Сен-Мартен) и Блонделя, ворота Святого Дионисия – там, где та же улица Блонделя пересекает улицу Святого Дионисия (Сен-Дени), Монмартрские ворота – на месте нынешнего дома 71 по Монмартрской улице, ворота Святого Гонория – на месте нынешней площади Андре Мальро.