Nel 1954 Enver Hoxha lasciò la guida del governo, affidandola al suo segretario, Mehmet Shehu; egli continuò tuttavia a dominare la vita politica del paese come leader del Partito del lavoro. I rapporti con il blocco sovietico iniziarono a deteriorarsi verso la metà degli anni Cinquanta, quando Hoxha si rifiutò di aderire alla destaliniazzazione voluta da Mosca e di acconsentire alla pacifica con i paesi capitalisti. Le opinioni politiche del governo albanese erano simili a quelle della Cina, con quale cercò un alleanza verso la fine del 1960,ma l'Unione Sovietica e i suoi alleati bloccarono tutti gli aiuti all'Albania e nel dicembre del 1961 il governo Mosca interruppe le relazioni diplomatiche.

L'invasione sovietica della Cecoslovacca, nel 1968, costrinse il governo albanese a rivedere la politica estera e la dipendenza dalla Cina.La riconciliazione fra Cina e Stati Uniti causò un raffreddamento di rapporti fra l'Albania e il governo Pechino che nel 1978 sospese tutti gli aiuti all'alleato balcanico. Rimaneva aperta la questione relativa alla minoranza greca in Albania e alla provincia del Kosovo, nella Serbia meridionale, con una forte minoranza albanese.