Approaches are described for automatically generating new security credentials, such as security tokens, which can involve automatically re-authenticating a user (or client device) using a previous security token issued to that user (or device). The re-authentication can happen without any knowledge and/or action on the part of the user. The re-authentication mechanism can invalidate and/or keep track of the previous security token, such that when a subsequent request is received that includes the previous security token, the new security token can be invalidated, and the user caused to re-authenticate, as receiving more than one request with the previous security token can be indicative that the user's token might have been stolen.