Temporal transaction locality in a stateless environment may be provided. First, a current message having an identifier may be received. Next, it may be determined, based on the identifier, that the current message is associated with a transaction. Then, in response to determining that the current message is associated with the transaction, the current message may be sent to a target service instance corresponding to the transaction.