Надя, тогда двадцатипятилетняя женщина, была сыта по горло своим положением тени великого вождя и приняла решение не быть больше «бабой». Вскоре после рождения Светланы она начала искать няню, которая могла бы заботиться о младенце, чтобы самой заняться своим образованием. Рассмотрев несколько кандидатур, Надежда остановилась на Александре Андреевне Бычковой.
Александра Андреевна хорошо знала, что такое преданность. Она родилась в 1885 году, в имении под Рязанью, к юго-востоку от Москвы. Там она была горничной, кухаркой, няней, домоправительницей, пока не переехала в Санкт-Петербург, в дом директора театра и критика Николая Евреинова, который до революции принадлежал к либерально настроенной интеллигенции. В его семье неграмотная Александра Андреевна научилась читать и писать. Когда Октябрьская революция заставила Евреиновых бежать в Париж, они предлагали Бычковой ехать с ними, но она отказалась покинуть Родину. В голодные двадцатые годы Александра Андреевна перебралась в Москву с единственным оставшимся в живых сыном (другой сын умер от голода). Здесь Бычкова встретилась с Надеждой Сталиной, которая и приняла ее на работу. По словам сводного брата Светланы Артема Сергеева, Бычкова была «просто чудесной няней». Она всегда напоминала ему знаменитую няню Пушкина Арину Родионовну.
Александра Андреевна замечательно рассказывала и народные сказки, которые слышала еще в своей деревне, и истории из «театральной» жизни в Петербурге. Речь ее была богата народными пословицами и поговорками. Но, с точки зрения хозяев, самым главным даром няни было умение хранить молчание обо всех неурядицах, с которыми она столкнулась в доме Сталина. Светлана говорила о ней так: «Всю мою жизнь она была для меня образцом спокойствия, трудолюбия, какой-то совершенно особенной невозмутимости и бесконечного оптимизма».