An authentication process receives information identifying a user, a device used by the user and a location in which the device is being used. That authentication process determines whether the location is among a set of familiar locations stored about the user for a service being accessed. If the location is not among the set of familiar locations, then the user is not authenticated. A desirable user experience can be obtained by using information about any existing relationship, such as a synchronization relationship, between the device and the service established at a prior familiar location. Instead of challenging a user whose device is in an unfamiliar location, the authentication process determines whether the device has a relationship established with the service. If the device has a relationship established with the service, then the set of familiar locations is updated to include the location in which the device is being used.