Брак Надежды и Иосифа был зарегистрирован 24 марта 1919 года. Но, по утверждению их дочери Светланы Аллилуевой, родители поженились еще весной 18-го, в самый канун переезда Совнаркома, где Сталин возглавлял наркомат по делам национальностей, из Петрограда в Москву. Для того времени такой разрыв между фактическим началом семейной жизни и официальным оформлением супружеских отношений был делом обычным. Многие десятилетиями жили в незарегистрированном браке. Например, маршал Г. К. Жуков свой первый брак не узаконивал более тридцати лет. Так что Иосиф с Надеждой, прожившие вместе без заветного штампа в паспорте всего год, выглядели даже немного старомодно.
Иосиф хотел, чтобы у Надежды родилась девочка. Когда на свет появился Василий, отец был огорчен. По свидетельству Фотиевой, тогда «Сталин перестал с Надей разговаривать… Не разговаривал целый месяц. Она решила уйти от него, переселиться к отцу. Произошло наконец объяснение. Сталин сказал, что обижен на нее за то, что она говорит ему «вы». После этого и она перешла на «ты». И помирились». Но окончательно Иосиф успокоился только через пять лет, когда родилась Светлана.
По утверждению племянника Надежды Владимира Аллилуева, ее ссора с Иосифом произошла еще до рождения Василия. В результате «перед родами Надежда ушла из дома, и никто не знал, где она находится. Родился Василий в каком-то родильном доме на окраине Москвы».
В том, что Иосиф со второй женой часто ссорились, сыграл свою роль и характер Надежды. Ее дочь Светлана вспоминает: «Мама была очень скрытной и самолюбивой. Она не любила признаваться, что ей плохо. Не любила обсуждать свои личные дела». К несчастью, теми же качествами обладал и Иосиф Сталин. А когда у обоих супругов такие характеры, конфликты в семье становятся неизбежными.
По свидетельству Фотиевой, Сталин загружал жену разными делами, диктовал ей свои статьи: «Она и его гостей должна была принимать, и работала машинисткой в секретариате Ленина. Однажды пришла и, взволнованная, сказала, что уходит с работы. Так он ей велел. Не оставалось у нее времени для него. Я пошла к Владимиру Ильичу и рассказала. Владимир Ильич сказал: «Если завтра не выйдет на работу, сообщите мне, я с ним поговорю».
Однако она вышла. Я сказала об этом Владимиру Ильичу. Он произнес: «Азиат».
Возможно, перед нами очередная красивая легенда о «добром» Ленине и «злом» Сталине. В действительности в 1921 году в связи с рождением сына Надежда ушла с работы и «за пассивность» в декабре того же года в рамках чистки была исключена из партии. Несмотря на заступничество Ленина, ошибку исправили и восстановили жену Сталина в партии только в 1924 году. Хотя Владимир Ильич 20 декабря 1921 года написал руководителям Центральной Контрольной Комиссии П. А. Залуцкому и А. А. Сольцу целое письмо в защиту Надежды Аллилуевой: «До меня дошло известие об исключении из партии Надежды Сергеевны Аллилуевой. Лично я наблюдал ее работу как секретарши в Управлении делами СНК, т. е. мне очень близко. Считаю, однако, необходимым указать, что всю семью Аллилуевых, т. е. отца, мать и двоих дочерей, я знаю с периода до Октябрьской революции. В частности, во время июльских дней, когда мне и Зиновьеву приходилось прятаться, и опасность была очень велика, меня прятала именно эта семья, и все четверо, пользуясь полным доверием тогдашних большевиков-партийцев, не только прятали нас обоих, но и оказывали целый ряд конспиративных услуг, без которых нам бы не удалось уйти от ищеек Керенского. Очень может быть, что, ввиду молодости Надежды Сергеевны Аллилуевой, это обстоятельство осталось неизвестным комиссии. Я не знаю также, имела ли возможность комиссия при рассмотрении дела о Надежде Сергеевне Аллилуевой сопоставить сведения об ее отце, который работал в разнообразных функциях по содействию партии (наверное, понять этот канцелярский оборот даже таким опытным бюрократам, как Сольц и Залуцкий, было непросто. —
Однако «комиссия по очистке» почти три года изучала дело Надежды, прежде чем согласилась его пересмотреть. Показательно, что до сих пор не обнаружено никаких документов, где Сталин заступался бы за жену в связи с ее исключением из партии. Может быть, Иосифа устраивало, чтобы Надежда была беспартийной, не пропадала целыми днями в Совнаркоме, а сидела дома, занималась детьми и выполняла функции его личного секретаря. Однако Надежда все же вернулась на службу в Совнарком, а позднее поступила учиться в Промышленную академию.