A wireless station prepares to roam by pre-authenticating itself with a neighboring access point. The wireless station sends a rekey request, which can include an incremented rekey number. The wireless station receives a rekey response. The rekey response can include the incremented rekey number. Because the wireless station is pre-authenticated, after it roams it only needs to perform a two-way handshake with a new access point to establish secure communications with the new access point. The two-way handshake starts by the wireless station sending a reassociation request to the neighboring access point, the reassociation request comprising the incremented rekey number established during pre-authentication. The wireless station receives a reassociation response from the neighboring access point. To protect against replay attacks, the neighboring access point can verify the rekey number sent in the reassociation request matches the rekey number sent in the rekey response.