THESSALONIKI, Greece — In a find that local Jewish groups have described as highly significant, Greek police said Thursday that hundreds of marble headstones and other fragments from Jewish graves destroyed during the Nazi occupation in World War II have been recovered.

The 668 fragments were found buried in a plot of land in Thessaloniki, Greece’s second largest city, following a 70-year search for the remains of graves smashed when the city’s main Jewish cemetery was destroyed.

The head of the city’s Jewish community, David Saltiel, said most of the gravestones found dated from the mid-1800s up until World War II....