Christianity emerged as a small and marginal movement in the first century Palestine and throughout the following three centuries it became highly visible in the whole Mediterranean. Little is known about the mechanisms of spreading innovative ideas in past societies. Here we investigate how well the spread of Christianity can be explained as a diffusive process constrained by physical travel in the Roman Empire. First, we combine a previously established model of the transportation network with city population estimates and evaluate to which extent the spatio-temporal pattern of the spread of Christianity can be explained by static factors. Second, we apply a network-theoretical approach to analyze the spreading process utilizing effective distance. We show that the spread of Christianity in the first two centuries closely follows a gravity-guided diffusion, and is substantially accelerated in the third century. Using the effective distance measure, we are able to suggest the probable path of the spread. Our work demonstrates how the spatio-temporal patterns we observe in the data can be explained using only spatial constraints and urbanization structure of the empire. Our findings also provide a methodological framework to be reused for studying other cultural spreading phenomena.