Office 365 Sync fails because of Conditional Access policies enabled on the service account

Problem

Office 365 Sync fails because of Conditional Access policies enabled on the service account.

Error Message

PowerShell connection attempt failed, check your information and try again.

Cause

The service account used for Office 365 Sync is unable to authenticate because of Conditional Access policies enabled on it.

In Azure Active Directory Admin Center, the below error message can be seen for the service account under Users -> ("Service Account") ->Activity -> Sign-ins.

Solution

1.Navigate to Azure Active Directory Admin Center using the Microsoft Admin Center and go to Enterprise Applications -> Security -> Conditional Access.
2.Review the Conditional Access policies and create exclusions for the service account used for the synchronization as required. 

Note : Microsoft's Conditional Access What If tool can also be leveraged to determine what all conditional access policies are associated with the service account being used. Documentation for the same can be found here : Troubleshoot using the What If tool in Conditional Access