We report on a new measurement of the CP-violating permanent Electric Dipole Moment (EDM) of the neutral $^{129}$Xe atom. Our experimental approach is based on the detection of the free precession of co-located nuclear spin-polarized $^3$He and $^{129}$Xe samples. The EDM measurement sensitivity benefits strongly from long spin coherence times of several hours achieved in diluted gases and homogeneous weak magnetic fields of about 400~nT. A finite EDM is indicated by a change in the precession frequency, as an electric field is periodically reversed with respect to the magnetic guiding field. Our result, $left(-4.7pm6.4right)cdot 10^{-28}$ ecm, is consistent with zero and is used to place a new upper limit on the $^{129}$Xe EDM: $|d_text{Xe}|<1.5 cdot 10^{-27}$ ecm (95% C.L.). We also discuss the implications of this result for various CP-violating observables as they relate to theories of physics beyond the standard model.