После окончания в 1919 году гимназии он поступил на физико-математический факультет Московского университета. Окончил его только в 1926 году из-за двухлетней службы в армии. Работал в Московском химико-технологическом институте им. Менделеева (1929—1934) и в МИАН АН СССР (1934—1975), с 1957 года — в должности заведующего отделом математической логики МИАН. Основные труды по теории множеств, математической логике, теории алгоритмов и теории групп. Создал школу математической логики в СССР. Награждён двумя орденами Ленина, орденом Трудового Красного Знамени. Ленинская премия (1957). Его учениками являются известные математики Адян С. И., А. А. Ляпунов, С. В. Яблонский, А. Д. Тайманов.
Ещё будучи аспирантом Н. Н. Лузина (1926 по 1929 год), П. С. Новиков получил полное решение одной из трудных проблем дескриптивной теории множеств с помощью разработанного им метода, получившего название «принцип сравнения индексов». Установил, что существуют группы с конечным числом образующих и конечным числом определяющих отношений, для которых не существует алгоритма, решающего проблему тождества слов. Создал метод доказательства непротиворечивости формальных систем, основанный на понятии регулярной формулы. Доказал неразрешимость проблемы тождества, сопряженности и изоморфизма в теории групп. Получил (вместе со своим учеником С. И. Адяном) отрицательное решение известной проблемы Бёрнсайда о периодических группах.
П. С. Новиков скончался после продолжительной болезни 9 января 1975 года. Похоронен на Новодевичьем кладбище вместе со своей женой Л. В. Келдыш.
Выдающиеся способности к точным наукам унаследовали его пасынок ( сын жены от первого брака), старший из детей, — Леонид Вениаминович Келдыш и сыновья: младший из детей, — Сергей Петрович Новиков и средний — Андрей, бывший доцентом Физико-технического института. В семье их были ещё две дочери: Нина и Елена.