Nas disputas majoritárias, em 2000, foi conquistada somente uma prefeitura (Olinda), pois o Partido se atrasou em relação à alteração na tática eleitoral para as disputas majoritárias. Fruto da correção que empreendeu a partir de 2004, em 2016 o Partido elegeu 82 prefeitos, entre eles Edvaldo Nogueira, eleito pela segunda vez prefeito de Aracaju. Edvaldo retoma e dá continuidade a uma gestão vitoriosa do seu primeiro mandato, que fez a cidade ser reconhecida como a “capital brasileira da qualidade de vida”. No Senado Federal, entre 2010 e 2014, o Partido ocupou duas cadeiras, pela primeira vez, sendo que em 2010 o PCdoB foi a quarta legenda mais votada para o Senado, mas em 2014 não elegeu senador e recuou a uma cadeira.