Pierwsza żona Kazimierza III Wielkiego była jednym z młodszych dzieci litewskiego księcia Giedymina, najprawdopodobniej ze związku z nieznanego bliżej pochodzenia Jewną. Dotychczas na podstawie przekazu Rocznika małopolskiego sądzono, że księżniczka urodziła się między 17 października 1309 a 16 października 1310, ale dokładna analiza źródłoznawcza przeprowadzona przez Jana Tęgowskiego zakwestionowała prawdziwość tej informacji.
Nie ulega jednak wątpliwości, że córka władcy Litwy w chwili ślubu ukończyła 12. rok życia. Najbezpieczniej możemy przyjąć, że Aldona Anna urodziła się między 1309 a 1313 – była zatem w podobnym wieku co jej przyszły małżonek. Wątpliwości budzi również kwestia pogańskiego imienia władczyni, Aldona. Jako pierwszy wymienia je dopiero XVI-wieczny historyk Maciej Stryjkowski. Na pewno Giedyminówna nosiła dwa imiona – jedno rodzime pogańskie, drugie przyjęte na chrzcie niedługo przed ślubem. Wobec braku innych przekazów pozostaje nam przyjąć informację Stryjkowskiego jako opartą na tradycji lub zaginionym źródle.
Sojusz przeciw Krzyżakom
W 1323 król Polski Władysław Łokietek, który wcześniej zaręczał swojego syna kolejno z córką króla Czech Jutą Luksemburską i księżniczką austriacką Anną, zwrócił swoją politykę dynastyczną w stronę pogańskiej Litwy, która podobnie jak Polska odczuwała zagrożenie ze strony zakonu krzyżackiego. Łokietek wysłał poselstwo do księcia litewskiego Giedymina z prośbą o rękę jednej z jego córek. Polski monarcha miał świadomość, że sojusz z poganami może zaszkodzić wizerunkowi państwa na arenie międzynarodowej.
W tym celu Giedymin zadeklarował chęć zapoczątkowania chrystianizacji swojego kraju, a w odpowiedzi papież wymógł na Krzyżakach czteroletni rozejm z Wielkim Księstwem Litewskim. Oczywiście król Polski nie uniknął oskarżeń o zdradę religii ze strony wrogiego zakonu, miał jednak wsparcie dla swoich działań ze strony Stolicy Piotrowej. Pod koniec 1324 na Litwę wyruszyło z Krakowa poselstwo, które w marcu 1325 przywiozło Aldonę Giedyminównę na Wawel.
Wkrótce po przyjeździe do Polski, najprawdopodobniej 30 kwietnia 1325 (Długosz podaje 28 czerwca) Aldona została ochrzczona przez biskupa krakowskiego Nankera. Księżniczka litewska przyjęła chrześcijańskie imię Anna, pod którym występuje we wszystkich współczesnych sobie źródłach.
Kazimierz Wielki i Aldona Anna zawierają małżeństwo
Związek małżeński między Aldoną Anną a Kazimierzem został zawarty 16 października 1325, a na ślubie obecni byli rodzice księcia oraz liczni dostojnicy polscy, między innymi biskup krakowski Maciej. Ślub odbył się z ogromnym jak na owe czasy przepychem, a jego bezpośrednim skutkiem było uwolnienie przebywających na Litwie jeńców wojennych, których liczba mogła sięgać nawet 24 tysięcy (jak podaje Stryjkowski).
Sojusz Polski z Litwą już wkrótce doprowadził do wspólnych wypraw wojennych: w 1326 na Brandenburgię, a w 1329 na ziemię chełmińską. Już jednak w 1330 doszło do pierwszych konfliktów między Władysławem Łokietkiem a Giedyminem i na prośbę Karola Roberta Andegaweńskiego Łokietek zaprzestał współpracy z pogańskim księciem. Od 1331 o wspólnej polityce ze wschodnim sąsiadem nie mogło być mowy.
Z małżeństwa Kazimierza i Aldony pochodziły dwie córki: urodzona między 1326 a 1330 Elżbieta oraz urodzona między 1327 a 1333 Kunegunda, które otrzymały imiona na cześć dwóch sióstr księcia Kazimierza.
W konflikcie z teściową
Już w pierwszych latach małżeństwa dwukrotnie było ono wystawione na próby. W sierpniu 1327 Kazimierz zachorował na nieznaną bliżej śmiertelną chorobę. Możemy się domyślać, że Aldona czuwała nad mężem, jednak to jego matka zwracała się z pomocą do papieża Jana XXII i powierzała życie syna św. Ludwikowi. Już wówczas dało się zauważyć antagonizmy między księżniczką litewską a jej teściową, które nasiliły się po śmierci Władysława Łokietka.