Конкурс на проектирование станции «Павелецкая» (радиальная) выиграли братья В. А. и А. А. Веснины, которые избрали темой оформления Донбасс. Проектным названием станции также была «Донбасская». Проект станции был похож на «Маяковскую» своей конструкцией — колонной, трёхсводчатой, здесь так же хотели использовать мозаику в оформлении (планировалось разместить 14 панно на своде центрального зала, эскизы которых исполнил А. Дайнека). Набор мозаик осуществлялся во время Великой Отечественной войны в блокадном Ленинграде В. А. Фроловым. В 1942 году готовые мозаики были доставлены, но металлоконструкции для новой станции остались в Днепропетровске, на временно оккупированной территории. Поэтому проект был изменён на двухсводчатую станцию без центрального зала с пилонным участком перед эскалатором. Восемь панно появились на соседней станции - Новокузнецкой. Временное оформление станции было начато архитектором Н. С. Князевым, затем продолжено совместно с А. Н. Душкиным.

Станция была открыта в составе третьей очереди строительства Московского метрополитена 20 ноября 1943 года на действующем перегоне «Площадь Свердлова» — «Завод имени Сталина». Первые полгода поезда следовали через «Павелецкую» без остановки из-за задержек в поставке эскалаторов. В связи с тем, что завод по производству эскалаторов находился в блокадном Ленинграде, заказ был передан московским предприятиям. В полном объеме станция заработала только летом 1944.

В 1948 году началась реконструкция станции по проекту, близкому к первоначальному (авторы — С. В. Лященко, Е. С. Демченко). Перестройка станции в колонную началась с короткого участка в три колонных секции у северного выхода. Этот участок станции открыли 21 февраля 1953 года вместе с эскалаторным наклоном в вестибюль «Павелецкой»-кольцевой. После этого перестройка осуществлялась между северным выходом и центром станции, этот участок открылся 30 июля 1955 года вместе с одним спуском в новый переход на станцию Кольцевой линии. Последний участок, от центра станции (включая второй спуск в переход) до сохранившегося поныне пилонного участка станции, был раскрыт к 20 апреля 1959 года. Реконструкцию пилонного участка возле южного выхода было решено не производить по причине необходимости закрытия на период реконструкции напряжённого выхода со станции на Павелецкий вокзал.

В 1982 году началась реконструкция Павелецкого вокзала, в результате которой южный вестибюль был встроен в увеличенное здание вокзала и перестроен.

Изначально вестибюль представлял собой отдельно стоящий павильон вблизи здания Павелецкого вокзала. На фасаде, выходящем на площадь, — четыре широких пилястра, между двумя из них пролёты использовались для входа и выхода, а средний — для большой мемориальной доски из красного гранита. Вход и выход размещались в симметрично расположенных глубоких и высоких полукруглых арках, снабжённых декоративными ажурными воротами. Снаружи фасад был облицован красным гранитом. Внутри павильон имел полукруглую стену с маленькими подковообразными окошками. По бокам от эскалатора раньше находились небольшие торшеры. Свод вестибюля был украшен плафоном, на котором было панно В. Ф. Бердиченко на тему славы русского оружия. Стена за эскалатором украшена мраморной мозаикой по эскизам Бердиченко на тему «Фанфарный салют народу и его вождю И. В. Сталину». После разоблачения культа личности Сталина его профиль был убран.

Со станцией связан один интересный факт: "Уважаемые пассажиры, будьте осторожны при выходе из последней двери последнего вагона". В Московском метрополитене это объявление звучит только в составах Замоскворецкой линии и только на станциях «Маяковская» и «Павелецкая». Дело в том, что длина платформы на этих станциях оказалась недостаточной для приёма восьмивагонных составов. В состав Замоскворецкой линии входят участки второй очереди строительства метро (1938 год), не приспособленных для восьмивагонных составов, которые появились в метро с ростом пассажиропотоков.

Когда составы на Замоскворецкой линии стали восьмивагонными, оказалось, что выход из последней двери последнего вагона на станциях «Маяковская» и «Павелецкая» не соответствует концу станции, а находится дальше. В этих местах удалось сделать только небольшое углубление в полметра шириной, фактически находящееся уже в тоннеле. Поэтому пассажирам, выходящим из последней двери последнего вагона на станциях «Павелецкая» и «Маяковская», следует быть особенно внимательными, чтобы не удариться при выходе о тюбинг тоннеля.