Examples relate to identifying heartbeat messages. In one example, a computing device may: obtain a plurality of messages that includes incoming messages and outgoing messages, each incoming message being sent from a server device to a client device, and each outgoing message being sent from the client device to the server device; identify candidate message pairs, each candidate message pair including one incoming message and one outgoing message; and identify a heartbeat message pair from the candidate message pairs based on at least one of: plurality of timestamps that includes i) incoming message timestamps that each correspond to one of the incoming messages, and ii) outgoing message timestamps that each correspond to one of the outgoing messages; a number of occurrences of each candidate message pair included a message log; or characteristics of data included in the incoming message and outgoing message of each candidate message pair.