With the rise of data-driven methods for traffic forecasting, accident prediction, and profiling driving behavior, personal GPS trajectory data has become an essential asset for businesses and emerging data markets. However, as personal data, GPS trajectories require protection. Especially by data breaches, verification of GPS data ownership is a challenging problem. Watermarking facilitates data ownership verification by encoding provenance information into the data. GPS trajectory watermarking is particularly challenging due to the spatio-temporal data properties and easiness of data modification; as a result, existing methods embed only minimal provenance information and lack robustness. In this paper, we propose W-Trace - a novel GPS trajectory watermarking method based on Fourier transformation. We demonstrate the effectiveness and robustness of W-Trace on two real-world GPS trajectory datasets.