[[File:Doctored Stalin-Lenin (cropped)(b).jpg|right|thumb|[[Josef Stalin]] pada sekitar tahun 1922.]]
Nadezhda Alliluyeva, lahir di Baku pada tanggal 22 September 1901<ref name="Ebon 40"/> sebagai anak bungsu dari empat bersaudara. Kakak-kakak kandungnya bernama Anna, Fyodor, dan Pavel.<ref>{{harvnb|Kun|2003|p=396}}</ref> Keluarga Alliluyev pindah ke [[Moskwa]] pada tahun 1904, tetapi kemudian kembali ke Baku pada tahun 1906. Pada tahun 1907, Sergei dan keluarganya pindah ke [[Sankt-Peterburg]] dan tinggal di sana untuk menghindari penangkapan.<ref>{{harvnb|Richardson|1993|pp= 29, 35–38}}</ref> Keluarga Sergei sering membantu menyembunyikan para anggota [[Bolshevik]], sebuah kelompok revolusioner Rusia, di rumah mereka, termasuk Stalin.<ref>{{harvnb|Kotkin|2014|p= 117}}</ref> Sergei Aliluyev bekerja di pembangkit listrik. Pada tahun 1911, ia diangkat sebagai kepala sektor di sana, sehingga memungkinkan keluarganya untuk hidup nyaman.<ref>{{harvnb|Richardson|1993|p=39}}</ref>
Nadezhda terlibat dalam aktivitas revolusioner selama masa mudanya,hal iniyang pertama kali terlihat ketika Nadezhda menjadi pendukung Bolshevik ketika masih bersekolah.<ref>{{harvnb|Richardson|1993|p=64}}</ref> Keluarganya sering menjamu anggota partai Bolshevik di rumah mereka, termasuk menyembunyikan [[Vladimir Lenin]] selama [[Hari-Hari Juli|Hari-hari Juli]] 1917, yang makin memperkuat pandangan revolusioner Nadezhda.<ref>{{harvnb|Richardson|1993|p=56}}</ref> Setelah Lenin melarikan diri dari Rusia pada bulan Agustus 1917, Stalin tiba.<ref>{{harvnb|Richardson|1993|p=62}}</ref> Ia telah mengenal Nadezhda sejak masih kecil dan Stalin diberitakan pernah menyelamatkan Nadezhda saat ia tenggelam ketika mereka berdua tinggal di Baku.<ref>{{harvnb|Montefiore|2007|p=194}}</ref> Setelah bertahun-tahun tidak berjumpa, pada suatu musim panas mereka menjadi dekat.<ref>{{harvnb|Montefiore|2007|pp=345–346}}</ref> Stalin dan Nadezhda akhirnya menikah pada bulan Februari atau Maret 1919.<ref>{{harvnb|Kotkin|2014|p=364}}</ref>{{Efn|Tanggal pernikahan tidak pernah tercatat.<ref>{{harvnb|Kotkin|2014|p=778, note 228}}</ref>}} Saat menikah, Stalin berstatus sebagai duda berusia 40 tahun dan ayah dari seorang putra ([[Yakov Dzhugashvili|Yakov]]) yang lahir pada tahun 1907 dari istri pertamanya, [[Kato Svanidze]], yang meninggal akibat [[Penyakit Rickettsia|tifus]] pada akhir tahun 1907. Tidak ada upacara pernikahan, karena kaum Bolshevik tidak menyukai kebiasaan tersebut.<ref>{{harvnb|Richardson|1993|p=69}}</ref>
