Впервые это поселение упоминается с 1566 года. В летописях тех времен поселение именуется Павловский Острог. Позднее стало именоваться дворцовое село Павлово, но еще долгое время селение называли по-старому – Павлов Острог. В чью же честь назван город? Краеведы и историки продолжают искать ответ на этот вопрос, так как в источниках прямое значение этого названия не указывается. Однако существует предание, согласно которого, Павлово основано при дороге, соединяющей Москву и Нижний Новгород, Павлом – перевозчиком. Эта легенда держится на том основании, что некогда это место именовалось, как Павлов Перевоз, а вот только после строительства крепости, получило новое название – Павлов Острог.