Enable Cloud Voicemail for an Office 365 User

Log into O365 Admin Portal and browse to active users:
https://admin.microsoft.com/Adminportal/Home#/users

Select each user, then select edit for the product licensing section:

Expand the Project Section which contains the users Skype Online license:

Find the Skype for Business Online Toggle:

Toggle the Switch On:

Find the Microsoft Teams Toggle and Toggle it On as well:

Repeat for all Users which need Cloud Voicemail Enabled.