Welcome to Android Central! Does your email service have a webmail interface? If so, log in with your computer browser and see if the emails are there.
If you're using a POP3 server and you had downloaded the emails to your phone, then deleted them from the server, then deleting the copies on the phone would be an irretrievable error (although check your email app to see if there's a Trash folder). This is why POP3 is such a bad idea -- it's outdated and obsolete. It's much better to use IMAP, which syncs your phone with the server in the cloud, thereby making it unnecessary to physically download your emails to your phone.