Some, especially "Товарищ Сталин, вы большой ученый" (Comrade Stalin, you are a great scholar [ru]) and "Окурочек" (Little cigarette butt), became extremely popular in the Soviet Union and are considered folk classics.

From the very beginning of his career, Aleshkovsky did not compromise his writing to conform to official Soviet doctrine, and for this reason his novellas and novels were available only in samizdat.

With no hope of being published officially in the Soviet Union, Aleshkovsky emigrated to the West in 1979 and waited for his entry visa to the United States in France and Austria.

His novel Kenguru (Kangaroo) tells the story of an old thief and his ordeals during the Stalinist era trials; Josef Stalin himself is a character.

His best-known and most appreciated works are his anti-Stalinist songs, which have become part of an urban folk tradition in the Soviet Union and are even mistakenly considered by some to be anonymous.