Accurate measurements of osculating orbital elements are essential in order to understand and model the complex dynamic behavior of Near Earth Asteroids (NEAs). ESA's Gaia mission promises to have great potential in this respect. In this article we investigate the prospects of constraining orbits of newly discovered and known NEAs using nearly simultaneous observations from the Earth and Gaia. We find that observations performed simultaneously from two sites can effectively constrain preliminary orbits derived via statistical ranging. By linking discoveries stored in the Minor Planet Center databases to Gaia astrometric alerts one can identify nearly simultaneous observations of Near Earth Objects and benefit from improved initial orbit solutions at no additional observational cost. ; Comment: Article accepted for publication in the proceedings of the International Symposium on Orbit Propagation and Determination held in Lille, France, 2011, to be published in 2014