Свои первые политические шаги Милюков связывал с деятельностью либерального движения девяностых годов, особенно с нелегальным буржуазным журналом «Освобождение». Журнал подготовил создание «Союза освобождения» (1903), нелегального политического объединения и стал его органом. Выработка собственной политической линии в идейном контакте с единомышленниками и в полемике с левым и правым течениями земского движения означала переход Милюкова от литературного сотрудничества к активному участию в политической борьбе. Милюков активно участвовал в многочисленных собраниях, где обсуждались проблемы и перспективы либерального движения. Программа журнала «Освобождение» в первоначальном варианте была написана Милюковым, обсуждена, одобрена и опубликована в первом номере журнала под названием «От русских конституционалистов». Программа провозглашала необходимость «серьезной политической реформы», постоянно действующего народного представительства с законодательными правами, что означало превращение России в конституционную монархию, отмены сословных привилегий, свободы личности, слова, печати, собраний и др. Основная задача его политической деятельности состояла в консолидации всех оппозиционных сил.
В своих статьях Милюков призывал создавать кадры убежденных конституционалистов и готовиться к созданию политической либеральной партии. В этом плане большое значение он придавал парижской конференции революционных и оппозиционных партий, состоявшейся в 1904 г., где председательствовал и в известной мере направлял ход ее работы. В резолюции совещания, составленной при участии Милюкова, формулировались общие цели борьбы с самодержавием, главной из которых была замена его демократическим строем, а также признавалась самостоятельность всех принимавших участие в совещании партий и разнообразие способов действия в достижении политической свободы.
Зимой 1904 г. Милюков приехал в Чикаго и сразу же начал читать курс лекций по истории славянства, там его и застали События русской революции 1905 года. Перед отъездом в Россию он спешно завершил работу над книгой «Россия и ее кризисы», вышедшей в 1905 году в Америке и во Франции, - в ней западной общественности был представлен русский либерализм, воплощением которого вскоре станет партия конституционных демократов. Для Милюкова было очевидно, что предсказанная им революция «действительно начинается». Теперь не было выбора: он должен вернуться в Россию.
Темой его «мощной политической пропаганды», того, что он называл «своей миссией», оставалась мирная парламентская работа. Обосновавшись в Москве, он сразу же вошел в кружок русских законоведов, занимающихся переработкой текста конституции, напечатанной за границей «Освобождением» и предназначавшейся для будущей партии. Авторитетные ученые и общественные деятели - М. М. Ковалевский, С. А. Муромцев, Ф. Ф. Кокошкин, П. И. Новгородцев, сам Милюков спорили о преимуществах однопалатной и двухпалатной парламентской системы, о принципах избирательного права, по крестьянскому и национальному вопросам.
Лето 1905 г. прошло у Милюкова в напряженной агитационной работе по созданию партии. На его первое публичное выступление собралась вся Москва, оно являлось «моментом» так называемого «официального принятия Милюкова в ряды русской общественности».
7 августа 1905 г. за публикацию в журнале «Сын отечества» статьи «Политическое значение закона б августа» Милюков был арестован в своем доме в Удельной, где у него собрались делегаты «Союза Союзов», политической организации буржуазной интеллигенции, созданной по профессиональному признаку, председателем которой он был избран в мае 1905 г. Полиция считала, что с изданием акта о Думе уничтожается действие указа от 18 февраля, который допускал открытое обсуждение преобразовании старого строя Милюкова опять поместили в «Крестах», где он просидел месяц.
Установление конституционного строя и создание для этой цели конституционной партии становилось "все более" его "личной задачей" .
Символично, что учредительный съезд конституционно-демократической партии, открывшийся 12 октября 1905 года, по заблаговременно составленным планам должен был завершиться 17 октября: как оказалось, именно в этот день был обнародован Манифест Николая II об изменении государственного строя. Политическая жизнь легализовывалась, и партия кадетов принялась энергично готовиться к выборам в I Государственную думу. В начале 1906 года, по оценкам Милюкова, партия насчитывала около 100 тысяч зарегистрированных членов. Ее наиболее активными в стране элементами были прогрессивные земские и городские деятели… Они были связаны и с народными низами, особенно через посредство так называемого «третьего элемента»: профессиональных служащих в земских учреждениях - врачей, агрономов, учителей и т. д.».
Первоначально Милюков был лишь одним из членов ЦК - бессменным председателем ЦК партии, а также ее главным идеологом, тактиком и стратегом он станет в 1907 году. Выдержав «вступительный экзамен на лидерство» на учредительном съезде партии, Милюков продемонстрировал, что способен быть консолидирующей фигурой. Позиция центристского большинства выражалась в программном тезисе о том, что «Россия должна быть конституционной и парламентской монархией» - тем самым снимался излишне радикальный лозунг «демократической республики». Вместо идеи «Учредительного собрания2 предлагалось сделать ставку на «Думу с учредительскими функциями» (бесспорной прерогативой парламента считалось принятие конституционных актов - Основных законов, нового избирательного закона, после чего Дума может потребовать своего роспуска). Самый острый для России земельный вопрос следует решить путем увеличения крестьянских наделов - за счет частичного отчуждения помещичьих владений с компенсацией «по справедливой оценке».
Милюков не смог избраться ни в Первую Государственную думу, ни во Вторую. Сказалось противодействие со стороны властей, хотя формальным предлогом для отстранения от участия в выборах стало несоответствие требованиям квартирного ценза. Тем не менее Павел Николаевич выступал в качестве фактического руководителя думской фракции кадетов. Говорили, что Милюков, ежедневно посещавший Таврический дворец, «дирижирует Думой из буфета».
Тактика кадетов, которую в конечном счете формулировал Милюков, ставила партию в жесткую оппозицию к власти. Хотя она подчас и корректировалась - в зависимости от политической конъюнктуры.
Впоследствии, в эмиграции, некоторые деятели кадетов будут обвинять Милюкова в том, что он после Манифеста 17 октября 1905 года, означавшего переход к конституционной монархии, не решился на однозначный разрыв с революционными силами и отказался от сотрудничества с «исторической властью», выдвигавшей тогда прогрессивных реформаторов. В столь жестких оценках есть доля истины, хотя нельзя не отметить попыток Милюкова поиска компромиссов (пусть и весьма условных). Например, вскоре после 17 октября лидер кадетов был приглашен в Зимний дворец на встречу с председателем Совета министров С. Ю. Витте. И главу кабинета удивило то, что Милюков, обычно обвинявшийся в радикализме, соглашался отказаться от требования «общественного министерства» - при условии, что Витте создаст «деловой кабинет» из незапятнанных чиновников-управленцев. На взгляд Милюкова, удовлетворить общество могло бы введение «сверху» умеренной конституции по образцу болгарской или бельгийской. В таком случае общественное мнение согласилось бы отказаться от идеи созыва Учредительного собрания. Но соглашение с кадетами и на подобных условиях оказалось для власти неприемлемым.
Конфликт с оппозиционным большинством I Думы, где более трети депутатов представляли кадетскую партию, был закономерен. Негативные последствия имело утверждение государем за несколько дней до созыва Думы Основных законов, что лишало парламент «учредительских» функций. Многие кадетские деятели, воодушевленные победой на выборах, были настроены радикальнее Милюкова и призывали к открытому конфликту с властью. Позже Павел Николаевич признавал, что стремился к «умерению политического темперамента Думы и усилению политической прозорливости власти», но «ни то ни другое, ни в особенности сочетание того и другого не оказались возможными ни для меня, ни для кого-либо другого». Пытаясь воспользоваться разногласиями в окружении царя, Милюков тайно встречался в ресторане «Кюба» с дворцовым комендантом Д. Ф. Треповым — сторонником уступок оппозиции и создания «министерства доверия». Трепов довел до сведения Николая II составленный им список кабинета, в котором Милюков фигурировал как кандидат в министры внутренних или иностранных дел. Перспективы формирования кадетского министерства обсуждались и с П. А. Столыпиным. Тем не менее развязкой конфликта власти и парламента стал роспуск Думы 9 июля 1906 года.
Учтя первый опыт парламентской борьбы, кадеты пересмотрели тактику. Революция шла на убыль, самодержавие доказало прочность своих позиций, и одновременно стало очевидно, сколь сильно сопротивление бюрократии и придворных кругов либеральным преобразованиям. Поэтому выдвигался лозунг: «Не штурм, а правильная осада». Предполагалось «беречь» II Думу, избегая прямых конфликтов, выражения недоверия правительству, чреватого роспуском парламента. Милюков считал, что теперь целесообразно дистанцироваться от левых, революционных сил. Несмотря на это, кадеты отклонили требование Столыпина - осудить в какой-либо публичной форме революционное насилие (за это была обещана официальная «легализация» партии). Павел Николаевич в принципе был готов напечатать в «Речи» такую статью без подписи, но другие лидеры воспротивились. Вскоре Думу распустили - под предлогом демонстративного отказа дать согласие на привлечение к уголовной ответственности социал-демократических депутатов.