Normally, the Messages icon shouldn't be available for deletion. It's considered as being a System application therefore the delete button shouldn't work. However, if the phone permitted this operation, then you will have to take different steps:
If it's a feature phone, it requires servicing from your local phone service or at the warranty service from your carrier.
If it's Android, install another SMS application (GO SMS from Play Store)
The iPhone or Windows phone devices don't allow this operation no matter you do.
