For a while now I’ve noticed that Messages on my phone was using 12GB of space. That seems like a lot, even Messages.app on my Mac doesn’t use nearly as much space. After a bit of research, I learned that there was a bug in Messages that attachments didn’t get deleted when the conversations were. Somewhere around iOS 6.0 or 6.1, this bug was fixed, but the stale attachments that were saved prior to this fix never got cleaned up. Deleting all the conversations doesn’t fix this as that won’t delete the stale attachments. There are 2 ways to fix this. Obviously, erasing and setting up your phone from scratch is one way. Another way is as follow:

• Backup the device to iTunes, I recommend encrypting the backup so you won’t have to re-enter passwords
• Open up the backup archive with a tool such as iBackupBot
• Duplicate the backup just to be safe
• Locate and delete the SMS data from backup archive (HomeDomain/Library/SMS and MediaDomain/Library/SMS)
• Restore device from said backup
• Enjoy re-claimed space on your iDevice

ref: Stratus Fear‘s post at MacRumors.