Gravitational waves cause the apparent position of distant stars to oscillate with a characteristic pattern on the sky. Astrometric measurements (e.g. those made by the Gaia spacecraft) provide a new way to search for GWs. The main difficulty facing such a search is the large size of the data set; Gaia observes more than one billion stars. I will discuss recent progress towards a practicable search for gravitational waves with Gaia and discuss the similarities with pulsar timing arrays.