An aspect of recovery from rolling security token loss includes storing, in a memory device accessible by a server computer, a token pair (B) transmitted to a client device. The token pair (B) includes an access token (a2) and a refresh token (r2) and is generated as part of a refresh operation. An aspect also includes storing, in the memory device, a refresh token (r1) that was generated by the server computer before generation of the token pair B. The refresh token (r1) and the refresh token (r2) are each tagged as a valid refresh token. An aspect further includes receiving, at the server computer, a request to access a network resource that includes the access token (a2), invalidating the refresh token (r1), and providing the client device with access to the network resource.