1 декабря 2001 года на учредительном съезде общественно-политических объединений "Единство" (лидер — глава МЧС Сергей Шойгу), "Отечество" (мэр Москвы Юрий Лужков) и "Вся Россия" (президент Татарии Минтимер Шаймиев) было принято решение о создании Всероссийской партии "Единство и Отечество — Единая Россия".
Сопредседателями номинального управляющего органа партии — высшего совета — избраны Сергей Шойгу, Юрий Лужков и Минтимер Шаймиев. Председателем генерального совета партии, осуществлявшего реальное руководство, и центрального исполкома партии стал бывший сотрудник мэрии Санкт-Петербурга Александр Беспалов. Однако вскоре, по данным СМИ, господин Беспалов начал вызывать недовольство в администрации президента своим стремлением узурпировать власть в партии, и его полномочия были урезаны. 20 ноября 2002 года новым руководителем единороссов стал глава МВД Борис Грызлов. Занимая министерский пост, он формально не мог возглавить генсовет, поэтому получил пост председателя высшего совета. Господин Беспалов возглавлял генсовет до 27 февраля 2003 года, когда стал начальником департамента информполитики "Газпрома". Председателем генсовета партии стал одногруппник Владимира Путина по Краснознаменному институту Первого главного управления КГБ, бывший кадровый разведчик Валерий Богомолов, главой исполкома — бывший сотрудник управления КГБ по Ленинграду и Ленинградской области Юрий Волков.
Третий партийный съезд 20 сентября 2003 года принял предвыборную программу. На съезде выступил Владимир Путин, пожелавший партии успеха на выборах. 7 декабря 2003 года "Единая Россия" убедительно выиграла парламентские выборы, получив 37,57% голосов, а вместе с одномандатниками — и конституционное большинство в нижней палате (сейчас во фракции 304 депутата). Борис Грызлов стал спикером Госдумы.
27 ноября 2004 года на пятом съезде партии была проведена реформа управления. Был ликвидирован центральный политический совет и введен принцип единоначалия, выразившийся во введении поста председателя партии. Председателем "Единой России" был избран Борис Грызлов.
В 2004-2005 годах партия участвовала во всех региональных выборах. Большинство из них партия выиграла, однако практически нигде не смогла повторить или превзойти результат, показанный ею на выборах в Госдуму. В четырех регионах "Единая Россия" проиграла выборы в региональные парламенты (в Алтайском крае, на Сахалине, в Корякском и Ненецком автономных округах). На губернаторских выборах единороссы потерпели три серьезных поражения: в Магаданской области 16 февраля 2003 года независимый кандидат Николай Дудов выиграл у представителя "Единой России" Николая Карпенко; в Рязанской области 28 марта 2004 года кандидат от "Родины" Георгий Шпак выиграл у члена "Единой России" Игоря Морозова; в Алтайском крае 4 апреля 2004 года сатирик Михаил Евдокимов победил поддержанного единороссами губернатора Александра Сурикова.