If you received a new email address they gave you the password as well (I assume). Don't you remember?
Call administrator of email accounts.
In case of hotmail, yahoomail, gmail... any webmail.... you can click "forgot password". Then you receive a secret question, or an email is sent to secundary mailaddress
Or is mailbox located at your internet provider? For example your provider is ZIGGO and your mailaddress is firstname.lastname@example.org