In an information processing system in which communication is performed using a IM server, a client connected to a NAT apparatus is capable of easily performing direct communicate with one of the other clients, regardless of whether or not the one of the other clients is connected with the same NAT apparatus as that with which the client is connected. Clients are registered beforehand in the IM server. When a first client wants to communicate with a second client, the first client requests, via the NAT apparatus, the IM server to determine whether the registered address of the first client is identical to the registered address of the second client. The IM server determines whether the addresses are identical to each other and the IM server informs the first client of the result of the determination. If it is determined that the addresses are not identical to each other, the first client performs communication with the second client on a global address basis. On the other hand, when it is determined that the addresses are identical to each other, the first client performs communication with the second client on a local address basis.