We analyze the existence, stability, and mobility of gap solitons in a periodic photonic structure with nonlocal nonlinearity. Within the Bragg region of band gaps, gap solitons exhibit better stability and higher mobility due to the combinations of non-locality effect and the oscillation nature of Bloch waves. Using linear stability analysis and calculating the Peierls-Nabarro potentials, we demonstrate that gap solitons can revive a non-trivial elastic-like collision even in the periodic systems with the help of nonlocal nonlinearity. Such interesting behaviors of gap solitons in nonlocal nonlinear photonic crystals are believed to be useful in optical switching devices.