This paper proposes a mechanism for sustaining privacy of a vehicle in a vehicular ad hoc network (VANET) through pseudonym update. In a VANET, vehicles on the road are involved in dissemination of information as they move. An association can be formed between the physical location of the source vehicle and the transmitted messages. This relationship between the physical vehicle and its identity can breach its privacy. In this work, a strategy for optimal pseudonym update for maximizing privacy has been formulated when a vehicle is being observed by adversaries with different capabilities. Results indicate that updating pseudonyms in accordance to the strategy maximizes the privacy of a vehicle in the given situation.