Родилась в семье революционера Сергея Яковлевича Аллилуева (1866—1945)  и его жены  Ольги Евгеньевны, урождённой Федоренко (1877—1951). Помимо Надежды, которая была младшим ребёнком супругов, в семье росли ещё два сына и дочь.

Иосиф Сталин познакомился с родителями Надежды Аллилуевой ещё в начале 1900-х годов в Тифлисе. Во время ссылки в Курейке он вёл с ними переписку. В 1917 году, после возвращения Сталина из ссылки, у них с 16-летней Надеждой завязались романтические отношения. В 1919 году они поженились. Разница в возрасте между супругами составляла 23 года.

В 1918 году Надежда вступила в РКП(б). Она работала в секретариате В. И. Ленина, который также был лично знаком с Аллилуевыми, в Наркомате по делам национальностей. В 1921 году, после рождения сына Василия, женщина прекратила активно участвовать в общественной и партийной деятельности. В декабре того же года она была исключена из партии как «балласт, совершенно не интересующийся партийной жизнью», но вскоре восстановлена как кандидат в члены РКП(б). В просьбе о восстановлении в партии жена Сталина обещала «подготовить себя для партийной работы».

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

8 ноября 1932 года Сталин и другие представители высшего руководства СССР с жёнами собрались в Кремле на праздничный ужин по случаю юбилея Октябрьской революции. В тот вечер между ним и Надеждой произошла ссора. В ночь на 9 ноября, вернувшись в кремлёвскую квартиру, женщина застрелилась из небольшого пистолета, подаренного братом Павлом.

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