An identity provider (IdP) discovery service operative at a service provider (SP) is described. In operation, and as valid requests are received by the SP via normal IdP-initiated flows, the SP builds-up knowledge about the relationship between the IdP (that redirected the request) and the initiator of the request. The IdP instance typically is inferred from an HTTP referrer field, and information about the initiator may be ascertained from client-specific information, such as client system IP address, client DNS domain, a domain of a user e-mail address, a target URL for the incoming request, or the value associated with a particular HTTP header field. This knowledge is maintained in one or more mapping table(s) that associate request attributes-to-IdP instance data. The mappings are then used to facilitate IdP discovery for a new incoming request to the SP that has been determined to originate from other than an IdP.