A TCP intermediate device receives a SYN packet from a TCP client that is destined for a TCP origin server and indicates support for TCP fast open (TFO). A SYN-ACK packet is transmitted to the TCP client that includes a first TFO cookie set by the TCP intermediate device. An ACK packet is received from the TCP client. A SYN packet is sent to the TCP origin server and a second SYN-ACK packet is received in response that includes a second TFO cookie set by the TCP origin server. An ACK packet to the TCP origin server. Sometime after the TCP connection is completed, a SYN packet from the TCP client is received that includes the first TFO cookie and a payload of data. The TCP intermediate device modifies the SYN packet to include the second TFO cookie and transmits the modified SYN packet to the TCP origin server.