Please clarify are they voice messages on the Voicemail or text messages through SMS?
Voicemail doesn;t work out of the box but has to be set up in Settings>My Device>Call. Some Service Providers can't or won't offer that facility even if the phone has it.