Provided are an apparatus and corresponding method of determining a navigation trajectory of a vehicle. The method includes receiving, by a control server, traffic congestion information with respect to a road network comprising trajectories from the current location to the destination, determining, by the control server, candidate trajectories ordered by the shortest distance among the trajectories from a current location to a destination or ordered by the shortest time among the trajectories from a current location to a destination, in consideration of the traffic congestion information, and determining, by the control server, the trajectory having the smallest increase in the traffic congestion degree with respect to the road network among candidate trajectories as a final trajectory.