De første som kom fram, var drøyt 130 fanger som ble løslatt ved Salem-kontrollposten nær byen Jenin på Vestbredden. Mange av dem viste V-tegnet da de gikk ut av bussene.
Løslatelsen av fangene er et resultat av fredssamtalene mellom Israel og palestinerne.
Ved flere andre kontrollposter hadde palestinske pårørende møtt opp med det palestinske flagget for å hilse fangene velkommen.
Dette er det største løslatelsen av palestinske fanger siden 1996, da 800 slapp fri. I løpet av de neste ukene skal til sammen 900 fanger løslates.
Ingen av fangene som nå slipper ut av fengsel er dømt for dødelige angrep. Alle har sonet mer enn to tredeler av straffen. Det sitter til sammen rundt 8.000 palestinere i israelske fengsler.
Militante grupper, som Hamas, har satt løslatelse av sine medlemmer som betingelse for en varig våpenhvile. Enkelte av de 500 som mandag ble sluppet fri, tilhører Hamas, men de fleste er med i Fatah-bevegelsen til president Mahmoud Abbas.
– Dette er ikke et enkelt skritt, men det er mulig at denne gesten både vil hjelpe de palestinske myndighetene med å etablere kontroll og at den vil øke den gjensidige tilliten mellom partene, sa Israels statsminister Ariel Sharon nylig.