I have tried the all mail option but my emails are not there. I have lost very important messages thinking I was putting them in a safe place but not.
How can I recover the messages?
The only way to lose a message is to delete it. Archiving a message will never delete it.
Assuming that a filter isn't used to automatically apply a label, the incoming email will only have the inbox label. As you work with the message you can manually add multiple labels.
The Archive command removes the inbox label from the message/conversation. If the user never added additional labels the only place to find it is in all mail. If the message/conversation had another label added to it, that label remains.
To find the email with a label you can use the sidebar listing of your labels, or use the search tool including the string "label:labelname" (don't include the quotes).