Frågan om invandring stod på spel i den sydvästra staten, det största priset i den senaste tävlingsrundan.
Undersökningar visade att Trumps anti-immigration budskap genljudde med statens konservativa väljare.
Med Arizonas växande latinobefolkning fortsatte Clinton sin framgång genom att uppvakta minoritetsväljare.
Under sin kampanj vann demokraterna Bernie Sanders målmedvetet kaukaser i två mindre delstater, Idaho och Utah.
Utah Republikanska kaukaser vanns av Texas senator Ted Cruz.
Han fick också ett välkommet uppsving med stöd av f.d. Floridaguvernör Jeb Bush, som drog sig ur loppet förra månaden.
Hillary Clinton och Donald Trump höll effektivt tjäna i tisdagens skiffer av primaries och kaukaser. Båda postade betydande vinster i Arizona, som - tack vare statens befolkning - balanserade ut förluster på annat håll.
För Mr Trump att ha en realistisk väg till säkra republikanska nomineringen innan partiets konvent behövde han Arizonas vinnare-ta-all primär. Staten visade sig vara bördig mark för front-runners anti-invandring, gränssäkerhet pitch.
Mr Trump är fortfarande på takten för att nära den magiska delegat nummer 1.237. Om inte farten förändras, blir det en nagelbitare.
New Yorkers Utah förlust var anmärkningsvärd för sin storlek, förneka honom några delegater där och bevisa att medan Mr Trump har bred vädjan bland republikaner, som inte sträcker sig till statens betydande mormon befolkning.
Det finns bara en Utah, men, och många fler stater framöver som kan vara vänligare till Mr Trump.
Mrs Clintons bekväma seger över Bernie Sanders i Arizona var mer förvånande, eftersom Vermont senatorn hade investerat betydande resurser där. Han dominerade dock de mindre Utah och Idaho caucuses - och erbjöd ytterligare bevis på sin vädjan i stater med en mindre varierad röstpool.
Sanders gjorde dock små, om ens några, framsteg i delegaträkningen. Han behöver fler stora vinster, utan bakslag som Arizona - och snart.
Under ett segertal i Seattle tog Clinton upp terroristattackerna i Bryssel i tisdags och stötte tillbaka mot de republikanska kandidaternas reaktion på bombningarna.
Tidigare på tisdagen upprepade Trump sin plan att förbjuda muslimer att resa till USA och föreslog att USA skulle tortera misstänkta för terrorism.
"Vi lever i en komplex och farlig värld", sade Clinton. "Och vi behöver en chefsbefälhavare som kan ge ett ledarskap som är starkt, smart och framför allt stadigt i att ta sig an dessa hot.
Det sista vi behöver är ledare som uppviglar mer rädsla, sa hon, anspelar på Mr Trump.
Den republikanska primären i Arizona var en vinnare-ta-all ras, lägga 58 delegater till Mr Trump betydande ledning.
Primära resultat 22 mars - Kompletta resultat från Arizona, Idaho och Utah
Trump kämpar för att vinna över mormoner - Till skillnad från andra religiösa grupper, Mormoner inte säljs på front-runner
Vem finansierar det amerikanska valet? - Pengar är en stor fråga i 2016 års amerikanska presidenttävling
Kan Hillary Clinton ställas inför fängelse? - Fallet med David Petraeus kan signalera hur hon kommer att klara sig
Den egendom tycoon vinna komplicerar ansträngningar av Cruz och Ohio guvernör John Kasich för att hindra honom från att säkra en majoritet av delegater.
Om Trump inte räcker till som delegat skulle partiet kunna hålla en mäklad eller ifrågasatt konvention där partiledare, inte väljare, väljer den nominerade.
Men detta scenario ser mindre troligt som Mr Trump fortsätter att vinna stater.
Arizona invånares preferens för tidig röstning, med många utskick i sina valsedlar, kan ha påverkat loppet.
Florida Senator Marco Rubio, som lämnade loppet den 15 mars, fick mer än 70.000 röster.
När de slutliga väljarna var på väg till opinionsundersökningarna på tisdagen, tog den republikanska rasen en annan otäck vändning.
Han trodde felaktigt att Cruz-kampanjen hade gett upphov till en attackannons om hans fru Melania, och Trump på Twitter hotade att "spilla bönorna" på Cruz fru Heidi.
Cruz svarade och sade att hans kampanj inte producerade annonsen, utan kallade Trump "klasslös" och "bytbar".
Amerikanska presidentledare, Democrat Hillary Clinton och Republikanska Donald Trump, har fortsatt sina vinnande strimmar, tar Arizona.