If you are facing this issue, you are not alone. In my case, I had run the install-Msolservice command before and it completed with no errors but nothing seemed to be installed, therefore it didn’t connect or recognize the modules in the machine. Here are the steps to get it fixed.
Open PowerShell as Admin –> Run the following commands in sequence (ensure your machine is connected to internet)
Firstly, uninstall the Azure-AD module
uninstall-module AzureAD
The re-install it
Install-module AzureAD
Install-module AzureADPreview
Try to run this. It will complete without any errors if you have the module existed but somehow corrupted (It could fail too but just run it anyways to verify)
Uninstall-module MSOnline
Now re-install the MSOnline Module
Install-module MSOnline
And now you can connect to O365. It should prompt you for credentials to login
Connect-MsolService
Once completed, the following command can be used to verify the installation.
Get-Module -ListAvailable -Name MSOnline*
Microsoft Cloud Infrastructure Technical Journal 