Described herein are methods and systems related to managing the storage of telephony-related data, such as calls, contacts, and/or messages. An illustrative embodiment receives media via a telephonic device. The media is stored in a first data store with a first degree of compression as a first file of a first size. A search interface is provided via which a user can search for the media. After a first period of time and/or at least partly in response to determining that the media has not been accessed or has been infrequently accessed, the media is stored in a second data store with a second degree of compression as a second file of a second size, wherein the second degree of compression is higher than the first degree of compression, and wherein the second size is smaller than the first size.