Methods and apparatus for use in providing map-related file data associated with point of interests for visually-displayed maps in mobile communication devices are disclosed. One illustrative method includes the steps of causing a viewable map region of a map to be visually displayed in a display of the mobile communication device, the viewable map region having one or more selectable map elements (e.g. selectable points of interest indicators or off-map indicators); monitoring to detect an end user selection of one of the selectable map elements through a user interface of the mobile communication device; causing information corresponding to the selectable map element to be visually displayed in the display in response to detecting an end user selection of one of the selectable map elements, the information including a file identifier corresponding to a file associated with the selectable map element; monitoring to detect, through the user interface, an end user selection of the file identifier or a file function identifier associated therewith; and causing, with use of a file link associated with the file identifier, file contents information of the file to be requested and received through the wireless communication network from a file server in response to detecting an end user selection. The file contents of the file are provided in a converted format (e.g. XML format) from the original file for suitable viewing in the mobile communication device. The file identifier may be or include, for example, a file type icon or a file name of the file. Preferably, data associated with the files are maintained in one or more public or private databases separate from the network database which stores map data for the common terrain features the map.