If you back up to iCloud or iTunes, and have not backed up since you deleted the messages, you can restore the backup and they will come back.
Caveat: You will lose all changes made to the phone since the last backup. Whether this is acceptable is entirely up to you.
Simply "erase all content and settings" and restore from the backup.
Read more:
How to Recover Deleted SMS from iPhone
iOS Data Recovery for iPad, New iPad, iPad Mini, iPhone 5/4/4S