Emergence of long-range phase coherence in nonlocal nonlinear media