A então senadora, Heloísa Helena, e os então deputados federais Luciana Genro, Babá e João Fontes foram expulsos do PT por votarem contra o projeto, pois entendiam que este tiraria direitos dos servidores públicos.
Buscando alternativas políticas à esquerda, os parlamentares citados iniciaram um movimento nacional pela fundação de um novo partido, de esquerda, socialista e democrático.
O novo partido obteve quase 700 mil assinaturas a favor de sua fundação, porém os cartórios eleitorais apenas concederam certidões a 450 mil dessas assinaturas. Os organizadores do partido fizeram uma nova tentativa em 1º de setembro de 2005 e, no dia 15 no mesmo mês, o registro definitivo foi obtido.
O PSOL recebeu apoio de intelectuais socialistas famosos, incluindo o geógrafo Aziz Ab’Saber, Fábio Konder Comparato, os sociólogos Francisco de Oliveira e Ricardo Antunes, dentre outros. Em 2005, o partido ganhou novas adesões, resultantes da crise política causada pelo escândalo do mensalão e pelas mudanças ideológicas do PT. Militantes históricos, fundadores do PT e petistas oriundos de movimentos sociais ingressaram no PSOL.
Em maio de 2006, durante a Conferência Nacional do partido, foi oficializada a candidatura da então senadora Heloísa Helena à Presidência da República. Heloísa foi presidente do PSOL entre 6 de junho de 2004 até 20 de outubro de 2010, quando renunciou ao cargo, logo após sua derrota na disputa pelo senado em Alagoas.
Em junho de 2013, o PSOL participou ativamente das grandes manifestações populares que irromperam no país.
O Partido Socialismo e Liberdade atuou em movimentos como o Fora Eduardo Cunha, CPI das Milícias, CPI da Dívida Pública, Fora Yeda, Movimento Ficha Limpa, manifestações contra a usina em Belo Monte, contra o trabalho escravo, dentre outros.