Navi Pillay föddes och växte upp i Durban. Hon tog 1967 sin juristexamen vid University of Natal och var därefter under apartheidregimen verksam med egen juristbyrå. Hon medverkade till att stärka rättigheterna för de politiska fångarna på Robben Island, däribland Nelson Mandela.