Techniques are provided for multi-tenant data protection using tenant-based token validation and data encryption. One method comprises obtaining, from a user, a data record to be stored in a multi-tenant storage environment and a token associated with the user. Each data record identifies a tenant associated with the respective data record and the user is authorized to access tenant data of at least one tenant identified in the token. An encryption key of the tenant associated with the data record is obtained and the data record is encrypted using the obtained encryption key and stored. A given data record may be read by obtaining a decryption key of the tenant associated with the given data record and decrypting the given data record using the decryption key. The token may be used to evaluate whether the user is authorized to access the tenant data of the tenant associated with the given data record.