A request to add tags (e.g., labels, key-value pairs, or metadata) to resources can be digitally signed by the entity making the request, such that the source can be verified and an authorization determination made for each tag. For a request involving multiple services (or entities) that can each add tags, any tag added by a service can be included in the request and digitally signed by that service. Each service processing the request can also digitally sign the request before forwarding, so that each service signs a version of the request, which includes elements signed by other services earlier in the request chain. When the request is received to a tagging service, the service ensures that every tag was digitally signed by the appropriate authorized entity or service, and validates the signatures to ensure that no data was modified or omitted, before adding the tags to the designated resource(s).