If you synced your phone before you cleared the history, then doing a Restore from back-up would bring it back.
1. Plug in your phone to your computer
2. In iTunes, under DEVICES, find your phone
3. Press Control + Mouse Click (Mac) Right Click (Windows)
4. Select Restore from Back-up
This process only takes a fews minutes, and doesn't delete any media or content, just the settings from the last time it was synced.