Handling of multiple connections during NAT traversal for a node behind a symmetric NAT is disclosed. The likelihood of connection failure during symmetric NAT traversal may be reduced by serializing critical time windows after port prediction. Once a connection request has been sent for a first connection, port prediction for a subsequent connection may be delayed until a connectivity check has begun for the first connection. This process may be repeated to handle NAT traversal for multiple simultaneous connections to different nodes.