Нова демокрация е учредена в края на 1995 г. от Иво Трайков, Николай Кисьов и Орлин Драганов - депутати от БББ в 37-ото народно събрание, напуснали Жорж Ганчев, отцепвайки част от Бизнесблока.
На конгрес на 6 март 1999 г. за председател на партията е избран Иво Трайков.
Приет е нов устав, според който досегашната форма на ръководство – трима съпредседатели (Кисьов, Драганов и Трайков) – е отменена.
Партията търсеше контакти с либералите на Луджев и Желев, но на форума си от 6 март 1999 г. тя се разграничава от ЛДС, защото не приема сътрудничеството на съюза със социалдемократите.
Конгресът се ориентира в местните избори да подкрепя ОДС и да търси контакти с ВМРО и БББ на Христо Иванов.