Don't worry, if you sync with iTunes, then you've got a backup.
I've just swapped to a new iPhone, and after sync'ing with iTunes and restoring from the backup that was automatically offered to me, everything was back exactly as before: contacts, messages, calendars, applications, everything. 🙂