Disclosed are various embodiments for performing stateless verification of communication addresses. Encrypted verification data is generated for a user account, including a communication address and a first verification code, and a timestamp. The encrypted verification data is sent to a client, and the verification code is transmitted to the communication address. The encrypted verification data and a second verification code are received from the client. The communication address is verified in response to observing that the first verification code from the encrypted verification data matches the second verification code.