Systems, methods, and computer-readable media for flow stitching network traffic flow segments across middleboxes. A method can include collecting flow records of traffic flow segments at a first middlebox and a second middlebox in a network environment including one or more transaction identifiers assigned to the traffic flow segments. Sources and destinations of the traffic flow segments can be identified with respect to the first middlebox and the second middlebox. Corresponding subsets of the traffic flow segments can be stitched together to from a first stitched traffic flow at the first middlebox and a second stitched traffic flow at the second middlebox. The first and second stitched traffic flows can be stitched together to form a cross-middlebox stitched traffic flow across the first middlebox and the second middlebox. The cross-middlebox stitched traffic flow can be incorporated as part of network traffic data for the network environment.