A relay device that relays a message transmitted from a terminal device to a server through a communications network. When a message is received from the terminal device, the relay device obtains attribute information related to the user of the terminal device, obtains an identifier to be inserted into a message to the terminal device by a server that generated a session in response to the message from the terminal device, the identifier being for identifying the session, stores the obtained identifier that is associated with the attribute information, determines whether or not the attribute information coincident to the attribute information obtained by receiving the message from the terminal device is to be stored when a message was received from the terminal device, inserts the identifier associated with the attribute information into the message received from the terminal device when the coincident attribute information is stored, and relays the message.