Nagluwas si Jolie sa saiyang pinakainot na pagganap sa Pushing Tin (1999), sarong pelikula na dai nagtabo sa takilya; alagad kan sumunod na pelikulang The Bone Collector (1999) ini nagin matriyumpo. Sa dramang Girl, Interrupted (1999), nagganap si Jolie sa sarong sosyopatikong mental na pasyente, sarong papel na nagtao saiya nin sarong Golden Globe Award asin sarong Academy Award for Best Supporting Actress. Sarong papel katambal si [Nicolas Cage]] sa pelikulang Gone in 60 Seconds (2000) an nagpatunay kan saiyang pinakamabentang pelikula sa puntong ini. Si Jolie nakua an pangkinaban na atensyon bilang sarong eponymous archaeologist sa Lara Croft: Tomb Raider (2001), sarong pelikulang aksyon na nakabase sa Tomb Raider video game series. Maski igwa nin mga negatibong tuyaw, nagkaigwa nin pinakadakulang ganar an pelikula sa inot na semana nin pagbukas kainitampok an bidang babaing heroe. Ini sinundan nin mga pagganap sa duwang pelikulang dai nagtabo sa takilya—an erotikong thriller na Original Sin (2001) asin romantikong komedyang Life or Something Like It (2002). Dai na inako ni Jolie an papel para sa sequel kan Lara Croft na igwang titulong Lara Croft: Tomb Raider – The Cradle of Life (2003).