Родился в городе Орёл в семье выходцев из Германии, принадлежавшей к разночинцам. Отец — Карл Андреевич Штернберг, подданный герцогства Брауншвейгского, был орловским купцом.
В 1883 году Павел Штернберг окончил Орловскую классическую гимназию.
В том же, 1883 году, он поступил на математическое отделение физико-математического факультета Московского университета и переехал в Москву. В университете Павел Штернберг стал одним из лучших учеников выдающегося астронома профессора Ф. А. Бредихина.
В 1887 году Павел Штернберг был награждён золотой медалью факультета за студенческую научную работу «О продолжительности вращения Красного пятна Юпитера». В мае этого же года он окончил университет.
Летом того же года Павел Штернберг участвовал в экспедиции Московской обсерватории в Юрьевец для наблюдения полного солнечного затмения 19 августа 1887 года. Кроме него затмение наблюдали А. А. Белопольский, а также Л. Нистен из Брюсселя и Г. Фогель из Потсдама.
Менее чем через год, в марте 1888 года, был назначен сверхштатным ассистентом Астрономической обсерватории и оставлен при университете для приготовления к профессорскому званию.
С 1890 года — приват-доцент университета. В том же году был утверждён в должности астронома-наблюдателя в обсерватории Московского университета.
В 1899—1900 годах возглавлял Комиссию по разработке программы по астрономии для средних учебных заведений.
После событий 1905 года в России Штернберг тайно вступил в РСДРП (б) и включился в подпольную работу в военно-техническом бюро московского комитета партии по подготовке вооруженного восстания.
Однако в дни самого восстания Штернберга в Москве не было. Он находился в заграничной командировке и вернулся только в начале 1906 года, после подавления восстания. По возвращении он включился в работу большевистской организации.
Оставаясь астрономом обсерватории, Штернберг выполнял поручения партии большевиков. Так, ему поручили сохранить отавшееся после Декабрьского восстания оружие, и часть его долго хранилась в обсерватории.
Во второй половине 1906 года в военно-техническом бюро РСДРП (б) на Штернберге лежала обязанность составления стратегической карты Москвы на случай нового вооружённого восстания и подготовки кадров командного состава для руководства боевыми действиями рабочих отрядов во время восстания. В 1907 году он осуществил смелое мероприятие по съёмке детального плана Москвы.
В 1908 году на выборах в Московскую городскую думу Павел Карлович был избран гласным по большевистскому списку.
С 1914 года — экстраординарный профессор Московского университета, а с 1917 — ординарный профессор.
В 1916 году 51-летний Павел Карлович возглавил Краснопресненскую обсерваторию.
В январе 1917 года был избран ординарным профессором астрономии Московского университета.
В марте был на совещании в Московском комитете партии большевиков о создании вооружённых отрядов.
3 (16) апреля 1917 года Штернберг присутствован на организованной Петроградским советом на Финляндском вокзале торжественной встрече вернувшегося в Россию Ленина. Слушал его выступление. Прямо с митинга он отправился на первый Всероссийский астрономический съезд, где за свои научные труды был избран председателем.
В апреле на очередном совещании Московского комитета Штернберг сделал доклад «О милиции». На съезде присутствовали Феликс Дзержинский, Григорий Усиевич, Розалия Землячка и другие. В действительности речь шла об организации Красной гвардии, о вооружении московских рабочих.
В обсерватории из трубы рефрактора вышла на свет карта Москвы. Московский комитет партии большевиков снял с неё копии и раздал по всем районным ячейкам.
По словам Я. Пече, в июле был создан оперативный штаб Красной гвардии по подготовке восстания. Этим штабом велась значительная работа по составлению стратегического плана восстания. Штернберг передал командованию Красной гвардии карты Москвы, составленные и хранившиеся им в подпольном архиве.
В конце октября 1917 года в дни восстания в Москве выделенный Московским комитетом партии большевиков боевой партийный центр назначил Штернберга уполномоченным партийного центра восстания по Замоскворецкому району. Это был наиболее сильный пролетарский район и именно оттуда должен был начаться обстрел Кремля.
Большевики Замоскворечья выступили на рассвете 28 октября. На Замоскворецкий район легла в основном задача по овладению штабом МВО (Пречистенка). Большую роль сыграло Замоскворечье и в овладении Кремлем и Александровским училищем. По инициативе и под его руководством Штернберга осуществлялся артиллерийский обстрел Кремля. Овладение Кремлём было главной задачей ВРК
В ноябре 1917 года его назначили военным губернским комиссаром Москвы.
В январе 1918 года губернский комиссар и профессор Высших женских курсов Павел Штернберг выдал «представляющие большую научную ценность» коллекции Дарвиновского музея, охранное удостоверение,.
В марте 1918 года, по совместительству, был назначен членом Коллегии Народного комиссариата просвещения и заведующим отделом высшей школы.
В ноябре-декабре 1919 года он принимал участие в руководстве боевыми операциями 3-й и 5-й армий Восточного фронта Рабоче-Крестьянской Красной армии по овладению Омском.
При форсировании Иртыша Штернберг тяжело заболел. Он был доставлен в Москву, где умер в ночь с 31 января на 1 февраля 1920 года.
Похоронен на Ваганьковском кладбище в Москве.
Жена — Яковлева, Варвара Николаевна (1884-1941), революционерка, советский государственный деятель.
Научные работы относятся к изучению вращательного движения Земли, фотографической астрономии, гравиметрии. За свои гравиметрические определения в ряде пунктов европейской части России с маятником Репсольда получил медаль Русского географического общества. В 1892—1903 гг. выполнил капитальное исследование «Широта Московской обсерватории в связи с движением полюсов».
Фотографические наблюдения двойных звёзд, которые проводил Штернберг, были одними из первых в науке строго разработанными попытками использования фотографических методов для точных измерений взаимного положения звёздных пар. Полученные им сотни фотоснимков двойных звёзд и других объектов служат и до настоящего времени хорошим материалом для специальных исследований.
В 1913 году Штернбергу была присвоена степень доктора астрономии в связи с защитой диссертации «Некоторые применения фотографии к точным измерениям в астрономии».
С 1931 года имя П. К. Штернберга носит Государственный Астрономический Институт Московского университета.
Именем П. К. Штернберга назван лунный кратер и малая планета 995 Sternberga (1923 NP).