Method of setting up a communication session between a calling client (C1) and a called client (C2), through a communication network (SN1, SN, SN2) containing at least one address translation device (NAT1, NAT2). This method contains stages for the transmission of signaling messages (fs), passing through at least one address translation device and allowing the exchange of the physical addresses of the clients. At least one of the clients implements a solution for the traversing of address translation devices. The method is innovative in that at least one client adds, within the sent signaling messages, a parameter representing the implementation of the traversing solution and that, in the presence of such a parameter, the network devices do not implement their own solutions for the traversing of address translation devices.