Новый этап развития города, который в конце 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 км2; далеко не вся эта территория была застроена; бóльшая часть ее была занята полями и виноградниками. Вне крепостной стены Филиппа II Августа на правом берегу Сены располагался замок Лувр, окруженный собственными укреплениями и рвом и таким образом защищенный от возможных нападений. К концу XIII века в Париже, согласно написанному около 1300 года «Сказанию о парижских улицах» поэта Гийо, насчитывалось 310 улиц: 36 на острове Сите, 80 на левом берегу и 194 на правом.
Город строился не только внутри крепостных стен, но и вне их; поэтому возникла необходимость расширить территорию, защищенную укреплениями. Следующая крепостная стена вокруг Парижа была построена спустя полтора столетия, в 1356–1383 годах. Начал ее строительство купеческий старшина Этьен Марсель, который реально правил городом после того, как король Иоанн II в сражении при Пуатье попал в плен к англичанам. Строительство продолжилось при короле Карле V, и стену принято называть его именем. На левом берегу эта стена практически повторяла предыдущую; работы состояли лишь в укреплении и обновлении старой крепостной стены Филиппа II Августа. На правом же берегу была построена новая стена общей длиной 4900 метров с шестью новыми воротами: ворота Святого Антония располагались на месте современной улицы Бастилии, ворота Тампля – там, где сегодня пересекаются улицы Тампля и Мелé, ворота Святого Мартина – там, где пересекаются нынешние улицы Святого Мартина (Сен-Мартен) и Блонделя, ворота Святого Дионисия – там, где та же улица Блонделя пересекает улицу Святого Дионисия (Сен-Дени), Монмартрские ворота – на месте нынешнего дома 71 по Монмартрской улице, ворота Святого Гонория – на месте нынешней площади Андре Мальро. Общая площадь территории, окруженной этой стеной, составляла 4,39 км2. Новая крепостная стена была устроена гораздо сложнее, чем предыдущая. Общая ее ширина составляла около 80 метров; вдоль укреплений 13-метровой высоты изнутри и снаружи шли дозорные пути, вдобавок вдоль стены был вырыт первый ров шириной до 30 метров и глубиной до 7–8 метров. За первым рвом шел второй, шириной 15 метров и глубиной 5,5 метра. Рвы были вырыты и вдоль вновь построенных участков стены, и вдоль тех участков старой стены Филиппа II Августа, которые сохранили свою оборонительную функцию. Память об этих рвах сохранилась в названиях некоторых парижских улиц, проложенных на их месте (например, улица Рва Святого Бернарда или улица Рва Святого Иакова).
Город продолжал развиваться, расти, и ему становилось тесно уже и в границах новых укреплений. Желая удержать парижан в пределах городских стен, король Франциск I в 40-е годы XVI века способствовал распродаже по частям территории многочисленных старинных особняков (домов, окруженных садами), результатом чего стали прокладывание и застройка новых улиц в черте города, таких как улица Карла V и Красивых Решеток, Французская улица и улица Барбета, улица Эльзевиров и улица Вишневого Сада. Согласно «Описанию Лютеции» Кнобельсдорфа (1543), улиц в Париже к этому времени имелось 500.
Множество новых улиц было проложено в начале XVII века по инициативе короля Генриха IV. При нем была создана Вогезская площадь и проложены по соседству с нею улицы в квартале Маре, создана площадь Дофина на острове Сите и проложена одноименная улица на левом берегу, построен Новый мост. Всего в царствование Генриха IV было проложено 68 новых улиц: 35 на правом берегу и 33 на левом. Импульс, данный Генрихом IV, не иссяк и после его смерти: в 1626 году подрядчик Шарло начал распродажу земельных участков в северной части Маре, результатом чего стало появление на карте Парижа нового квартала, улицы которого в большинстве своем получили имена французских провинций (Пуату, Сентонжская, Бретонская и др.).
В 1634 году кардинал де Ришелье начал строить поблизости от Лувра дворец, который впоследствии получил название Пале-Руаяль (то есть Королевский дворец), а поначалу назывался Кардинальским,