In 1955 the Belgrade Declaration restored Soviet-Yugoslav friendship and reinstated Tito to the fraternity of world communist leaders. Because Chervenkov had branded Tito and the Yugoslavs as arch-villains during his rise to power, this agreement eroded his position. Then, in February 1956, Nikita S. Khrushchev denounced Chervenkov's patron Stalin and Stalin's cult of personality at the twentieth congress of the CPSU. Unwilling to stray from the Soviet party line, the BCP also condemned the cult of personality (and, implicitly, Chervenkov's authoritarianism), advocating instead collective leadership and inner-party democracy. In his 1956 report to party leaders, Zhivkov expressed this condemnation and promised that the party would make amends for past injustices--a clear reference to the fate of Kostov and Chervenkov's other purge victims in the party. Having had his entire regime repudiated by the party leader, Chervenkov resigned. Zhivkov, who had thus far remained below Chervenkov in actual party power, now assumed the full powers of his party first secretary position. The 1956 April Plenum became the official date of Bulgarian de-Stalinization in party mythology; after that event, the atmosphere of BCP politics changed significantly.

Data as of June 1992