A method and system is described for using a conversation-based messaging system. When a messages is received by the system an attempt is made to associate the message with an existing conversation, if any. If there is no existing conversation to which the message belongs, a new conversation is created. The message is then associated with the existing or new conversation and may be provided certain initial attributes. Information about the message including certain indexing information is stored in memory for the respective conversation. The text of message is indexed along with other information and stored in memory for subsequent searching.