Disclosed is a system and method for connection of host behind network address translators. The system includes a server placed in a public network, and a transparent middleware (TMW). The server records the related data between each host and one or more NAT devices. The TMW may be performed in each host. When a first host of a first NAT device tries to establish connection to a second host of a second NAT device, through the server, the TMW looks up a first IP address mapping from the first host to the second NAT device, and a second IP address mapping from the second host to the first NAT device. Accordingly, the TMW accomplishes the support for establishing connection between the first and the second hosts.