Example methods and systems for flow-based latency measurement for logical overlay network traffic are described. In one example, in response to detecting a first inner data packet associated with a packet flow, a first computer system may generate and send a first encapsulated packet via a logical overlay tunnel towards a second computer system. The first encapsulated packet may be generated by encapsulating the first inner data packet with a first outer header that includes first time information associated with the first inner data packet at the first computer system. In response to detecting a second encapsulated packet from the second computer system via the logical overlay tunnel, the first computer system may determine a flow-based latency measurement associated with the packet flow based on the first time information, and second time information identified from a second outer header of the second encapsulated packet.