Always-on localization is an important problem for a lot of context sensitive mobile computing applications. This paper proposes WaveLoc, which effectively uses measurements from a trajectory as its fingerprint for localization. Different from traditional approaches, which use signatures from single-points for localization, we leverage signatures from a trajectory, since it offers a lot more information. However, it is much more challenging to match measurements across trajectories than from single points. To tackle this challenge, WaveLoc divides the problem into the following two steps: (i) identify a user's current trajectory by matching its measurements with those in the training traces (trajectory matching) and (ii) localize the user on the trajectory (localization). The core requirement of both steps is an accurate and robust algorithm to match two time-series that may contain significant noise and perturbation due to differences in speed, mobility, devices, and environment. WaveLoc addresses these by performing multi-level wavelet analysis of the measurements and applying an enhanced Dynamic Time Warping (DTW) alignment to the wavelet coefficients. Using both indoor and outdoor experiments, we demonstrate that WaveLoc is accurate and power efficient.