I had some hard times to setup PowerShell access to Office365, so I summarized the steps below to successfully setup.
Step 1: Download and install Microsoft Online Services Sign-In Assistant
Step 2: In services.msc, start “Windows Remote Management (WS-Management)” service
Step 3: Start PowerShell as Administrator and execute following
Step 4: Follow the steps mentioned in the below microsoft article to get connected to Office365 through PowerShell
$UserCredential = Get-Credential $Session = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUri https://outlook.office365.com/powershell-liveid/ -Credential $UserCredential -Authentication Basic -AllowRedirection Import-PSSession $Session