 On the breakup of the Roman Empire , Gaza became part of the Byzantine Empire as part of the Palaestina Prima province . The official recognition of Christianity by Constantine I did not increase sympathy of the religion in Gaza . Although Gaza was represented by Bishop <unk> in the First Council of Nicaea in 325 , the vast majority of its inhabitants continued to worship the native gods . As the Roman Empire was crumbling at this time , Gaza remained unaffected . At this time , the inhabitants of Maiuma converted to Christianity en masse . Constantine II decided to separate it from pagan Gaza in 331 , giving Maiuma its own episcopal see . Julian reversed the process during his reign in the latter half of the 4th century . Although Maiuma had its own bishop , clergy , and diocesan territory , it shared its magistrates and administration with Gaza . Upon Julian 's death , Maiuma 's independence was restored and the rivalry between it and Gaza intensified . 
