Map labels are dynamically downloaded to a wireless communication device for efficiently labelling a map displayed on the device. A method of dynamically downloading map labels to a wireless communications device includes steps of determining a size of label data for an area of interest and dynamically downloading the label data for the area of interest based on the size of the label data. Optionally, map labels can be dynamically downloaded based on a label prioritization scheme that takes into account the current position of the device. Optionally, the size of the label data can be determined from a map data index.