Data tags, such as may be used to classify data, can be automatically applied at appropriate times in a resource environment. A customer can provide an auto-tagging configuration file that can be used to determine tags to be applied to specific data objects based upon properties of those objects. The customer can also provide policies that indicate which actions can be performed for those objects based at least in part upon the applied tags. The tags can be automatically applied at any appropriate time, such as upon storage into the environment, upon modification of the auto-tagging configuration, or upon modification or the data object. In some embodiments, an auto-tagging process can also be performed in response to a request for access to the data object in order to ensure that the correct tags are applied before determining the permitted actions.