It quickly grew in number of believers and influence over a few decades , and by the 4th century had become the dominant religion in the Roman Empire . Originating in the eastern Mediterranean coast of the Middle East ( modern Israel and Palestine ) , it quickly spread to Syria , Mesopotamia , Asia Minor and Egypt , it grew in size and influence over a few decades , and by the 4th century had become the dominant religion within the Roman Empire .