My message icon has been deleted. How do I recover it?

Messages is one of the things you can't delete.

Don't do a factory reset just yet. Start by resetting your Home Screen Layout. Settings>General>Reset>Reset Home Screen Layout. You'll lose folders that you put applications in but, in my opinion, it's a lot faster than restoring the phone.

For future reference:

Remove built-in Apple apps from the Home screen on your iOS 10 device or Apple Watch - Apple Support

Go to Settings-General-Reset and reset all settings.

Go to the app store, and search for messages. when you see it load, hit the "download" icon.

madra31 wrote:

Go to Settings-General-Reset and reset all settings.

If you want to reset your iPhone to factory defaults. Just be carful on "what" you delete.