ПСПУ була створена в квітні 1996 року. Ініціаторами її створення стали колишні члени СПУ, народні депутати України - Наталія Вітренко і Володимир Марченко.
З моменту створення ПСПУ позиціонувала себе як партія, яка відрізняється від СПУ і КПУ, які, на думку лідера прогресивних соціалістів - Наталії Вітренко, пішли на угодовство з тодішньою владою.
Лідери партії
Наталія Вітренко, Володимир Марченко.
Участь в президентських виборах
Під час виборів 1999 року Наталія Вітренко посіла четверте місце (10,97%). Правда, Наталія Михайлівна стверджує, що перемогу у неї вкрали.
У 2004 році кандидат на пост глави держави Вітренко на президентських виборах здобула підтримку 1,53% тих українців, хто проголосував.
Участь у парламентських виборах
Під час виборів 2002 року блок Наталії Вітренко не подолав 4-відсоткового бар'єру (3,22%). Як вважає лідер ПСПУ, результати парламентських виборів були сфальсифіковані. Кілька спроб отримати депутатський мандат у мажоритарних округах в Черкасах, Мелітополі, Чернігові для Наталії Вітренко були невдалими.
Під час виборів 2006 року блок Наталії Вітренко "Народна опозиція" отримав підтримку 2,93% і не потрапив в український парламент. Спроби ПСПУ оскаржити результати виборів виявилися невдалими.
1 травня 2002 року Наталя Вітренко оголосила про створення в державі "Народної опозиції".
Підтримка
Міністр внутрішніх справ Юрій Луценко заявляв, що нині покійний російський бізнесмен Максим Курочкін ("Макс Скажений") причетний до ПСПУ і має серйозні претензії до Наталі Вітренко. Лідер ПСПУ відкинула звинувачення. Хоча сам Курочкін публічно заявляв, що симпатизував ПСПУ.