 In September 1993 , leaders of Israel and the PLO signed the Oslo Accords calling for Palestinian administration of the Gaza Strip and the West Bank town of Jericho , which was implemented in May 1994 . Israeli forces withdrew from Gaza , leaving a new Palestinian National Authority ( PNA ) to administer and police the city . Led by Yasser Arafat , the PNA chose Gaza as its first provincial headquarters . The newly established Palestinian National Council held its inaugural session in Gaza in March 1996 . 
