Немалое место в публикациях о Сталине, особенно распространившихся в годы перестройки, занимали слухи о его сотрудничестве с царской охранкой. Некоторые исследователи утверждают, что такие обвинения впервые были выдвинуты против него еще в дореволюционное время. Однако никаких документальных подтверждений наличия таких обвинений нет.

Правда, в двадцатые годы, во время острейшей борьбы Сталина с троцкистами, его противники пытались распускать подобные слухи, но тогда они были лишь устными и вскоре прекратились. Позже эти слухи опубликовал в эмигрантской прессе руководитель меньшевиков Ной Жордания, но они также не получили распространения.

23 апреля 1956 года в американском журнале «Лайф» появилась статья «Сенсационная тайна проклятия Сталина». Она принадлежала перу бывшего ответственного работника ОГПУ—НКВД Александра Орлова (Льва Фельбина), который в 1938 году, опасаясь ареста, бежал в США с поста резидента НКВД в Испании. Время для ее публикации автор выбрал как нельзя лучше: только что Хрущев выступил с резкой критикой Сталина на XX съезде КПСС, что вызвало всплеск интереса к личности диктатора, умершего три года до этого.

Помимо первой статьи, Орлов опубликовал ряд других. Он объявил, что настало время раскрыть такую темную тайну о бывшем вожде, которую даже Хрущев не разоблачил. Она, по его словам, заключалась в том, что Сталин был осведомителем Охранного отделения и перед революцией выдавал своих товарищей-большевиков. Орлов писал, что его коллега по НКВД Штейн якобы еще в 1937 году обнаружил в архиве тайной полиции папку с агентурными донесениями Иосифа Джугашвили заместителю директора Департамента полиции Виссарионову. Ссылаясь на рассказы тех, кто якобы знакомился с содержанием этих документов, Орлов утверждал: Сталин был агентом полиции вместе с Малиновским, но «решил устранить Малиновского со своего пути на секретной работе в Охранке» и с этой целью написал в полицию письмо против этого провокатора.