A method and apparatus for searching message data in a portable electronic device are provided. A threaded message inbox is provided at a display of the device, the message data grouped as threads. Search criteria are received and a search of an index of the threaded message inbox is initiated using the search criteria, the index comprising key words extracted from the message data. Additional message data is received while the search is being performed, the additional message data belonging to a given thread. Additional message data is searched in addition to the index. Search results are generated based on whether at least one of data from additional message data and data from the index meets the search criteria. Search results are provided in threads at the display. Search results are automatically updated in response to receiving additional message data when the additional message data meets the search criteria.