Anna Walentynowicz urodziła się 15 sierpnia 1929 roku we wsi Sienne (obecnie Sadowe), na Rówieńszczyźnie należącej do ówczesnej Polski. Jej rodzice, Nazar Lubczyk i Pryśka z domu Paszkoweć, wyznawali sztundyzm. Był to głęboko pietystyczny nurt protestancki, zrodzony na Ukrainie w środowisku niemieckich kolonistów w XIX wieku, zdobywający zwolenników wśród ludności miejscowej. Jak nietrudno zgadnąć, w tej konfesji państwo Lubczykowie wychowali swoje dzieci, a więc również Annę, która chrzest w obrządku katolickim przyjęła dopiero w latach 60., przed wstąpieniem w związek małżeński.

Późniejsza bohaterka „Solidarności”, wcześnie osierocona przez matkę, pozostawała pod opieką swego biologicznego ojca oraz macochy do 12 roku życia. Zdążyła ukończyć cztery klasy szkoły powszechnej (podstawowej). Dalsza edukacja została jednak gwałtownie przerwana przez atak nazistowskich Niemiec na ZSRS w roku 1941.