An apparatus comprising memory access circuitry to perform a tag-guarded memory access in response to a received target address and methods of operation of the same are disclosed. In the tag-guarded memory access a guard-tag retrieval operation seeks to retrieve a guard tag stored in association with a block of one or more memory locations comprising an addressed location identified by the received target address, and a guard-tag check operation compares an address tag associated with the received target address with the guard tag retrieved by the guard-tag retrieval operation. When the guard-tag retrieval operation is unsuccessful in retrieving the guard tag, a substitute guard tag value is stored as the guard tag in association with the block of one or more memory locations comprising the addressed location identified by the target address.