Neutron powder-diffraction experiments on La2/3Ca1/3MnO3 over a broad temperature range above and below the metal-insulator transition have been analyzed beyond the Rietveld average approach by use of reverse Monte Carlo modeling. This approach allows the calculation of atomic pair distribution functions and spin-correlation functions constrained to describe the observed Bragg and diffuse nuclear and magnetic scattering. The results evidence phase separation within a paramagnetic matrix into ferromagnetic and antiferromagnetic domains correlated to anisotropic lattice distortions in the vicinity of the metal-insulator transition.