In order to connect to O365 via PowerShell proceed with the following.
Start PowerShell as an admin.
$UserCredential = Get-Credential
$Session = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUri https://outlook.office365.com/powershell-liveid/ -Credential $UserCredential -Authentication Basic -AllowRedirection
Import-PSSession $Session
Use the following command to end the Session
Remove-PSSession $Session