Džoli je počela da radi kao manekenka sa 14 godina. Potpisala je za Fajnes model Menadžment (Finesse Model Management) i radila kao manekenka u SAD i Evropi, radeći uglavnom u Los Anđelesu, Njujorku i Londonu. Takođe se pojavljivala u mnogobrojnim muzičkim spotovima, uključujući one za Mit Louf („Rock'n'Roll Dreams Come Trough“), Antonelo Venditi („Alta Marea“) i Lenija Kravica („Stand by My Woman“). Sa 16 godina Džoli se vratila u pozorište, i tamo je glumila svoju prvu ulogu kao nemačka „dominatriks“. Počela je da uči od svog oca, nakon što je uočila njegovu metodu posmatranja ljudi da bi se postalo kao oni. Njihova veza u to vreme je bila manje napeta, a Džoli je uočila da su oboje „kraljice drame“.
Džolijeva se pojavila u 5 studentskih filmova njenog brata, snimljenih dok je on pohađao Školu filmskih umetnosti kalifornijskog univerziteta, ali njena profesionalna filmska karijera počela je 1993 kada je odigrala prvu vodeću ulogu u niskobudžetnom filmu Sajborg 2, kao Kasela "Keš" Ris, skoro ljudski robot, napravljena da zavođenjem prokrči sebi put u sedište suparničkog proizvođača i da se tamo samo-detonira. Nakon nekoliko neuspešnih projekata zasijala je kao Kejt Libi u svom prvom holivudskom filmu, „Hakeri“ (1995.), gde je upoznala svog prvog muža Džonija Li Milera. Njujork Tajms je pisao, „Kejt (Andželina Džoli) razbija. To je zato što se mršti još kiselije nego [drugi glumci] i ona je retka žena haker koja namerno sedi za tastaturom u providnoj majičici. Uprkos njenom natmurenom stavu, koju ova uloga zahteva, gospođica Džoli ima istu slatku [heruvim]sku pojavi kao i njen otac, Džon Vojt.“ Film nije napravio neki profit, ali je nakon izdavanja za video stekao kultno sledbeništvo.
1996. se pojavila kao Đina Malačiči u komediji Love Is All There Is, modernoj slobodnoj adaptacija Romea i Julije, postavljenoj između dve suparničke italijanske porodice-vlasnike restorana u Bronksu u Njujorku. U filmu Mojave Moon bila je tinejdžerka po imenu Elenor Rigbi koja se zaljubila u Denija Ajela, koji je zavodi njenu majku, En Arčer. Takođe 1996. u filmu Foxfire je odigrala ulogu Margaret „Legs“ Sadovski, jedne od pet tinejdžerki koje zasnivaju neočekivanu vezu nakon fizičkog obračuna sa profesorom koji ih je seksualno zlostavljao. O njenoj izvedbi Los Anđeles Tajms je napisao: „U razvoju ovog lika mnogo je besmislica, Džoli, prelepa ćerka Džona Vojta, ima dovoljno snage da prevaziđe stereotip. Mada je Medi pripovedač priče, Legs je njen subjekat i katalizator."
1997. Džoli je glumila sa Dejvidom Duhovnijem u trileru Igranje boga (Playing God), film oslikava poznatog hirurga iz Los Anđelesa kome je oduzeta medicinska dozvola i koji je umešan duboko u kriminalni svet gde upoznaje Andželinin lik, Klaru. Film nije dobro primljen od strane kritičara i Rodžer Ebert govori da „Andželina Džoli pronalazi određenu toplinu u ovakvoj ulozi koja je obično teška i agresivna; izgleda previše fino da bila devojka kriminalca, a možda i jeste.“ Onda se pojavila u filmu Prava žena, istorijska romantična drama koja se odigrava na divljem zapadu, i zasnovana je po knjizi Dženiz Vuds Vindl. Glumila je i striptizetu u muzičkom spotu Roling Stonsa za pesmu Anybody Seen My Baby?
Karijera joj je krenula uzlaznim tokom nakon uloge Kornelije Valas u biografskom filmu Džordž Valas (1997.) za koji je osvojila nagradu Zlatni globus i bila nominovana za Emi. Film je bio visoko ocenjen od strane kritike a, između ostalih nagrada, primila je Zlatni globus za „Najbolju miniseriju/film napravljenu za TV“. Glumila je drugu ženu bivšeg guvernera Alabame koji je, u toku kandidature za predsednika, ranjen u atentatu i ostaje paralizovan. Glavna uloga u filmu je poverena Gariju Sinisu, a režirao ga je Džon Frankenhajmer.
1998. Džolijeva je igrala glavnu ulogu u TV filmu Đia, snimljenom u produkciji kuće HBO, biseksualnu manekenku, Điju Karanđi. Film opisuje svet seksa, droge i emocionalnih drama, prikazuje hronologiju propasti Karanđine karijere što je bio rezultat njene zavisnosti od droge, i njenu smrt zbog SIDE. Drugu godinu za redom, Andželina osvaja Zlatni globus i biva nominovana za nagradu Emi. Takođe osvaja svoju prvu nagradu Udruženja filmskih glumaca.
U skladu sa metodom glume Lija Strasberga, Andželina voli da ostane u liku koji glumi i između scena, za vreme snimanja filma, i kao rezultat dobija reputaciju glumice sa kojom se teško sarađuje. U vreme snimanja filma Đia, rekla je svom tadašnjem mužu Džonu Li Mileru da neće moći da ga zove. "Rekla sam mu: Sama sam, umirem, ja sam gej. Neću te videti nekoliko nedelja."
Nakon filma Đia, Džoli se preselila u Njujork i prestala da glumi u jednom kratkom vremenskom periodu zato što je osećala da „nema više ništa da pruži“. Upisala je studije režije na njujorškom univerzitetu i pohađala časove pisanja. U emisiji Inside the Actors Studio objasnila je da je dobro za nju da se sabere.
Vratila se na veliko platno 1998. ulogom Glorije Mekniri u gangsterskom filmu Đavolja kuhinja (Hell's Kitchen), a kasnije te godine je postala deo odabrane glumačke postave koja uključuje Šona Konerija, Džilijen Anderson, Rajana Filipa i Džona Stjuarta u filmu Playing by Heart. Drama priča o nekoliko naizgled nepovezanih karaktera, a Džolijeva igra mladu posetiteljku noćnih klubova, Džoan. Film je dobio pretežno pozitivne kritike, a Džolijeva je bila posebno pohvaljena. Za ovu ulogu osvojila je nagradu Breakthrough Performance koju dodeljuje National Board of Review.
Andželina je 1999. glumila u komediji-drami „Kontrolni toranj“ (Pushing Tin) Majka Njuela, o dva kontrolora leta koji se nađu u mačo konfliktu, zajedno sa Džonom Kjuzakom, Bilijem Bobom Torntonom i Kejt Blenčet. Džoli igra Torntonovu zavodljivu ženu Maribel. Film je imao mlak prijem kod kritike, a lik koji je glumila Džoli je posebno kritikovan. Vašington Post piše, Mari (Andželina Džoli), potpuno smešna piščeva kreacija slobodoumne žene koja plače za hibiskusom koji vene, nosi mnogo tirkiznog prstenja i biva poprilično usamljena kada Rasel provodi cele noći van kuće.“Potom je glumila pored Denzela Vošingtona u filmu „Sakupljač kostiju“ (The Bone Collector), snimljenom po adaptiranom krimi romanu koji je napisao Džeferi Diver. Džolin lik, Amelija Donahju, je policajka koju proganja samoubistvo njenog oca policajca. Ona nevoljno pomaže Vašingtonu da prati i uhvati serijskog ubicu. Film je imao bruto zaradu 151 milion dolara od projekcija širom sveta, ali ga je kritika loše ocenila; Detroit Free Press je zaključio: „Džolijeva, koju je uvek divno gledati, je jednostavno loš izbor za ovu ulogu.“
Džoli zatim dobija sporednu ulogu Lize Rou, u filmu Neprilagođena (Girl, Interrupted), u kome glavnu ulogu tumači Vinona Rajder. Film govori o lečenju Suzane Kejsen u bolnici za mentalne bolesti, a scenario predstavlja adaptirane originalne memoare Suzane Kejsen, izdate pod nazivom Girl, Interrupted. Iako je glavnu ulogu imao lik Vinone Rajder, a film je trebalo da predstavlja njen povratak na scenu, ispostavilo se da je bio "dobrodošlica u Holivud" za Džoli. Osvojila je treći Zlatni globus, drugu nagradu Udruženja fimlskih glumaca i Oskara za najbolju žensku sporednu ulogu.
Godine 2000. Džoli se pojavljuje u prvom letnjem blokbasteru „Minut za beg“ (Gone in Sixty Seconds), kao Sara "Svej" Vejlend, bivša devojka kradljivca kola koga glumi Nikolas Kejdž. Uloga je bila mala, a Vašington Post piše „sve što radi u ovom filmu je da je prisutna, kulira, pokazuje te mesnate, pulsirajuće usne koje tako provokativno uokviruju njene zube.“ Kasnije je objasnila da joj je ovaj film bio dobrodošlo olakšanje nakon zahtevne uloge Lize Roj, a postao je film od koga je, do tada, najviše zaradila - 237 miliona dolara od projekcija širom sveta.
Mada je visoko cenjena zbog svojih glumačkih sposobnosti, Andželinini filmovi nisu često zadovoljavali široki auditorijum, ali ju je Lara Kroft: Tomb Rajder (2001.) napravio filmskom zvezdom. Za adaptaciju popularne video igrice Tomb Raider, od Džolijeve je traženo da usavrši britanski akcenat i da se podvrgne žestokom treningu da bi odigrala ulogu Lare Kroft. Andželina je bila uglavnom pohvaljivana za svoju ulogu, ali je film uglavnom izazvao negativne kritike. Slent Magazin je komentarisao: „Andželina Džoli je rođena da odigra Laru Kroft, ali je režiser Simon Vest od njenih avantura napravio igru Frogger.“ "Ipak, film je imao ogroman međunarodni uspeh, zaradivši 275 miliona dolara širom sveta, a ona je tada stekla reputaciju međunarodne zvezde.
Džolijeva je zatim glumila pored Antonija Banderasa, kao mlada Džolija Rasel u „Prvobitnom grehu“ (Original Sin), triler zasnavan po noveli „Valcer u tami“ Kornela Vulriha. Film je uglavnom imao loše kritike, uz komentar Njujork Tajmsa: „Priča potapa okomitije nego dekolte gospođice Džoli.“ 2002. je glumila Leni Kerigan u filmu „Život ili nešto slično“ (Life or Something Like It) o ambicioznoj TV reporterki kojoj je rečeno da će umreti za nedelju dana. Film je loše primljen od strane kritičara, mada je Andželinina gluma dobila pozitivne kritike.
Džolijeva je 2003. reprizirala ulogu Lare Kroft u filmu „Lara Kroft Tomb Rajder: Kolevka života“. Nastavak nije bio tako unosan kao original, pošto je zaradio 156 miliona dolara širom sveta. Kasnije te godine Džolijeva je glumila u „Izvan granica“ (Beyond Borders), filmu o humanitarnim radnicima u Africi. Iako film reflektuje Andželinino pravo životno interesovanje u promociji humanitarne pomoći, film je bio kritički i finansijski neuspešan.
Godine 2004. Džolijeva je glumila uz Itana Houka u trileru „Uzimanje života“ (Taking Lives), kao Ileana Skot, agent FBI-ja pozvana da pomogne montrealskoj policiji da uhvati serijskog ubicu. Film je dobio različite kritike, a Holivud Reporter je zaključio: „Andželina Džoli igra ulogu koju definitivno oseća kao nešto što je već radila, ali ona dodaje nepogrešivu crtu uzbuđenja i opsene.“ Andželina je takođe posudila glas Loli, anđeoskoj ribici u animiranom filmu Drimvorksa Priča o ajkuli (Shark Tale); u filmu glume još Vil Smit, Martin Skorseze, Rene Zelveger, Džek Blek i Robert de Niro. Takođe u 2004, Džolijeva je imala kratko pojavljivanje kao Frenki u „Nebeskom kapetanu i svetu sutrašnjice“ Kerija Konrana, naučno-fantastičnom avanturističkom filmu u celosti snimanog sa glumcima ispred plavog ekrana, sa skoro svim scenama i rekvizitima urađenim putem računarske animacije.
Džoli je zatim odglumila Olimpiju u „Aleksandru“, biografiji Olivera Stouna o životu Aleksandra Velikog. Film je loše prošao u SAD, što je Stoun pripisao lošem prijemu zbog neslaganja sa prikazom Aleksandrove homoseksualnosti, ali je na međunarodno sceni, sa prihodima od 139 miliona dolara izvan Sjedinjenih Država.
Andželinin jedini film u 2005, akciona komedija „Gospodin i gospođa Smit“ (Mr. & Mrs. Smith), je do sada njen najveći komercijalni uspeh. Film, koji je režirao Dag Liman, prikazuje priču o dosadnom paru u braku koji saznaje da su oboje tajne ubice. Džolijeva je glumila Džejn Smit, uz Breda Pita. Film je bio dobro primljen i uglavnom je bio pohvaljen za „hemiju“ između glavnih glumaca. Film je zaradio preko 478 miliona dolara širom sveta, i jedan je od najvećih hitova 2005.
Andželina se zatim pojavila u „Dobrom pastiru“ Roberta de Nira, o ranoj istoriji CIA, viđene kroz oči Edvarda Vilsona, kojeg je odigrao Met Dejmon. Džolijeva je glumila Klover Vilson, Vilsonovu zanemarenu suprugu, koja postaje alkoholičarka tokom radnje filma.
Andželina je potvrdila buduće projekte uključujući animirane filmove „Beovulf“ (igraće Grendelovu majku) i „Kung-fu panda“, kao i „Ogromno srce“ (A Mighty Heart), film zasnovan na životu Danijela Perla, novinara Volstrit Džurnala koji je kidnapovan i ubijen u Pakistanu; glumiće Perlovu ženu Marijanu Perl. Takođe će se pojaviti u filmskoj adaptaciji knjige Revoltirani Atlas (Atlas Shrugged), a i kruže glasine da će biti angažovana u Gradu greha 2.