Methods, devices, and systems are provided for verifying tokens using limited-use certificates. For example, a user device can send a token request to a token provider computer, and receive in response a token and a token certificate associated with the token. The token certificate may include, for example, a hash of the token and a digital signature by the token provider computer or another trusted entity. The user device can provide the token and the token certificate to an access device. The access device can verify the token using the token certificate, and verify the token certificate using a digital signature. In some cases, the token and token certificate may be verified offline. The access device can then conduct a transaction using the token.