La libertad sexual era uno de los derechos de las primeras mujeres revolucionarias de aquella Rusia y ellas también compartían los mismos riesgos en la lucha que los hombres, aunque eso no significa que los bolcheviques no fueran machistas.
Stalin había sido uno de los amantes de Olga, la madre de Nadia; incluso se ha analizado la posibilidad de que fuera el padre de ésta, pero esa teoría se da por tierra porque los datos precisos indican que Stalin conoció a los Alliluyev cuando Nadia ya tenía tres años.
Uno de los hechos más curiosos en la vida de Stalin y Nadia ocurrió cuando el futuro dictador aún vivía con Kato en Bakú, donde en ese momento también residían los Alliluyev. Un día la pequeña Nadia estaba jugando en su terraza y cayó al mar Caspio. Stalin, que se hallaba en el lugar, saltó a las aguas y consiguió rescatarla salvándole la vida. Después de ese incidente Stalin y Nadia volvieron a verse cuando él tenía cuarenta años y ella diecisiete.
Tanto Nadia como sus hermanos —Fiodor, Pavel y Ana— se criaron en una casa —o casas, porque cambiaban de domicilio en forma permanente— que era un verdadero centro revolucionario. Allí se desarrollaban intensas reuniones políticas y también era un lugar al que acudían los camaradas a refugiarse de la persecución policial. No era raro que su padre desapareciera del hogar al ser buscado por las autoridades, o que regresara golpeado y lastimado tras los interrogatorios. Según Reyes Blanc esas circunstancias modelaron el carácter de Nadia, un carácter “abnegado, corajudo, tenaz, fanático en su ideología, pero con un déficit emocional y una inestabilidad que derivarían en patológicos. Lo necesario para ser una buena revolucionaria, pero no para llevar una vida feliz en familia”.
Stalin fue una presencia habitual en la casa de los Alliluyev, a la que volvió en muchas oportunidades. Reyes Blac explica que, “para los chicos, era una especie de tío bromista y divertido, que cantaba, hacía imitaciones y contaba chistes, y de quien se relataban proezas revolucionarias. Desde la perspectiva actual nos parece mentira, pero Stalin se entendía bien con los niños, era cariñoso y comprensivo con ellos… aunque fuera capaz de abandonar a sus propios hijos sin el menor escrúpulo”.
Al hablar de su relación con Nadia, sostiene: “En 1917 ella estaba enamorada de él con toda seguridad, y probablemente también él de ella, y no hay duda de que consumaron su amor en 1918, cuando se vieron juntos en el frente de guerra, combatiendo a la contrarrevolución en la remota Tsarytsin, pues volvieron formando una pareja de hecho y se casaron en 1919”.