Krestovsky came from an old family of Polish gentry (szlachta) with roots in nowadays Ukraine.

At the university he became friends with the radical critic Dmitry Pisarev, and wrote for the magazine Russian Word.

[1][2] After his short association with the radical camp, he joined a group of moderate slavophiles which included Apollon Maykov, Lev Mei and others, and began publishing his works in Notes of the Fatherland, Time and Epoch.

His novel The Slums of Saint Petersburg (1864), a product of many hours of personal observation, gained him considerable popularity.

[1][2] In 1863 he traveled to Warsaw to take notes for his novel The Flock of Panurge (1869), about the January Uprising.