 During most of the 4th century , the Christian community was small , poor , and carried no influence in the city . The church was insignificant and its members were not allowed to hold political office . However , conversion to Christianity in Gaza was spearheaded under Saint Porphyrius between 396 and 420 . In 402 , after obtaining a decree from the emperor , he ordered all eight of the city 's pagan temples destroyed and idol worship was forbidden by the Byzantine government . Paganism continued and Christians were still persecuted in the city , forcing St. Porphyrius to undertake more measures . As a result of his persuasion , Empress Aelia Eudocia commissioned the construction of a church atop the ruins of the Temple of Marnas in 406 . ( Note that according to MacMullen it is likely that Porphyrius did not even exist . ) Persecution against Christians did not cease , but it was less harsh and frequent than previously . A large 6th century synagogue with a mosaic tile floor depicting King David was discovered in Gaza . An inscription states that the floor was donated in 508 – 509 CE by two merchant brothers . Around 540 , Gaza became the starting point for pilgrimages to the Sinai Peninsula . It was an important city in the early Christian world and many famous scholars taught at its academy of rhetoric , including 6th @-@ century scholar Procopius of Gaza . The celebrated Church of Saint Sergius was built in this century . 
