Antonio Rodolfo Oaxaca Quinn 1915. április 21-én született Mexikóban, Chihuahuában. Édesanyja azték, édesapja ír gyökerekkel rendelkezett. Antonio katolikus neveltetésben részesült, szülei papot szerettek volna belőle nevelni, ám a fiú tizenegy évesen pünkösdista lett. Aimee Semple McPherson gyülekezetébe látogatott el, akiről később azt mondta, hogy Zorba megformálásában az evangélista hölgy ihlette meg, aki híres volt prédikációinak színházi előadások segítségével történő átadásáról.
Mivel Anthony szülei részt vettek egy diktatúraellenes forradalomban, az Egyesült Államokban kezdett tanulni, ahol először hobbiszinten, majd profi pályát is fontolgatva az ökölvívásban próbálta ki magát. Apja korai halála miatt kénytelen volt eltartani magát, a bokszolás mellett fizikai munkával kereste kenyerét: dolgozott cementipari munkásként és taxisofőrként is, de volt gyümölcsszüretelő munkás és cipőtisztító is. Bár a fiú villanyszerelést és asztalos mesterséget tanult, majd építészeti tanulmányokat is folytatott, a világhírű építész, Frank Lloyd Wright rábeszélte, hogy forduljon a színészet felé.
A fiatalembert, markáns vonásaira felfigyelve, egyre gyakrabban hívták statisztának, majd kisebb darabokban is szerepeket kapott, de jó ideig még a stáblistában sem szerepelt a neve. 1947-től 1950-ig a Broadway-en játszott, kimagasló szerepei azonban nem voltak.