In vehicular ad-hoc networks (VANET), which has high node mobility, location based routing is more scalable and incurs lower overhead compared to the address based routing protocols. In providing location based routing, vehicle location service, which tracks the location of moving vehicles and provides correct location information of a target vehicle in the VANET, is essential. In recent year, the vehicle location service is researched which reflects characteristic of VANET, i.e., high mobility of the vehicle, a wide moving range and limited moving path along the road layout, however, in existing methods, performance is degraded since location of server is limited to geographical areas. In this paper, we propose the vehicle location service using the vehicle trajectory. Since the location server is moving together with the vehicles receiving the service, geographical proximity between the location server and the vehicles can be maintained while the mapping between the location servers and the vehicles lasts long due to the characteristics of VANET mobility, i.e., majority of the vehicles running on the same road segment move with a similar trajectory maintaining the proximity for a while. Through a simulation, the performance of the proposed mechanism is compared with an existing approach. The simulation results show that the proposed mechanism provides more accurate location discovery service with lower overhead.