Described herein are systems, methods, and software to manage maximum segment size (MSS) values associated with multiple tunnels according to an implementation. In one implementation, a gateway may obtain a Transmission Control Protocol (TCP) synchronize (SYN) packet from a computing node. The gateway may identify a tunnel associated with the TCP SYN packet, determine a maximum segment size (MSS) value based on the overhead associated with the tunnel, and replace a first MSS value in the TCP SYN packet with the MSS value determined by the gateway. Once added, the gateway may encapsulate the TCP SYN packet and communicate the packet to a second gateway.