A capability is provided for statelessly load balancing Transmission Control Protocol (TCP) connections across a set of servers. A load balancer receives a TCP SYN packet from a client, selects a server for a TCP connection for the client, forms a modified TCP SYN packet including an address of the client, and propagates the modified TCP SYN packet toward the server. The server receives the modified TCP SYN packet, forms a TCP SYN+ACK packet including an identifier (e.g., n bits of an address, an n-bit server index based on mapping information of the load balancer, or the like) of the server, and propagates the modified TCP SYN+ACK packet toward the load balancer. The load balancer receives a TCP packet from the client on the TCP connection, determines a server associated with the TCP connection based on information included within the TCP packet, and propagates the TCP packet toward the server.