W roku 1915 Tajtelbaum wstąpił do gimnazjum w mieszczącej się przy ul. Klonowej Szkole Mazowieckiej. W jego zakresie nauczania były wtedy niemiecki, francuski, łacina, historia, religia, prawo, logika, matematyka, fizyka, kosmografia (obejmująca astronomię, geografię i geologię) oraz higiena. W gimnazjum tym nauczano też nowo wprowadzonego języka polskiego i polskiej literatury. Chociaż świadectwo końcowe Alfreda nie wymieniało języka greckiego, to niewątpliwie wtedy zapoznał się on z greką. Posługiwał się też płynnie językiem rosyjskim. W zapiskach nauczycieli przedstawiany był jako uczeń o niezwykłych zdolnościach.
W 1923 Alfred Teitelbaum – wraz z bratem Wacławem – zmienił nazwisko na „Tarski”. Oprócz zmiany nazwiska na polskie bracia zmienili religię z wiary żydowskiej na katolicyzm. W przypadku Tarskiego miało to wyłącznie znaczenie symboliczne, bo faktycznie pozostał on do końca życia ateistą. Tarski był polskim patriotą, który uważał siebie za Polaka, jednocześnie nie chcąc być Żydem także z powodu międzywojennego antysemityzmu, który blokował Żydom możliwość zrobienia kariery uniwersyteckiej. Wszędzie popierał on polskich logików, a jego dom w Berkeley zawsze otwarty był dla Polaków.