A system and method are provided for receiving navigational data via a wireless messaging service on a navigation system. The system and method provides a way to send requests for destination information via the wireless messaging service and capture navigational data from the responsive message received, such as addresses, telephone numbers, or email addresses, and then utilize that data for navigational routing, generation of telephone calls, emailing and the like, from the vehicle's navigation system. A wireless device can be paired with the navigation system over a Bluetooth communication link, wherein the navigation system periodically polls the wireless device for newly received messages. In one embodiment, the NAVI displays icons on a map that correspond to the extracted addresses from the messages received in relation to the vehicle's current location. The icons can be shown in a plurality of visual formats to distinguish previously viewed locations from newly received ones.