Automated device discovery of pairing-eligible devices for authenticating an unidentified user of a computing device is provided. When the user initiates a login on the computing device on which the user's identity is not known, an automated pairing-eligible device discovery authentication system interrogates a resource (e.g., subnetwork router, calendaring server) for identifying pairing-eligible devices that may be used as a second factor for authentication. A list of the pairing-eligible devices is presented to the user on the computing device. Upon selection of a pairing-eligible device to use as a second factor to verify the user's identity, the user's identity is determined, and a notification is sent to the selected pairing-eligible device for enabling the user to verify his/her identity using a second factor. Upon completion of an authentication challenge on the selected pairing-eligible device, authentication of the user is completed, and a signed token is sent to the computing device.