In order to permit a video telephone call to be set up between at least one first video telephone terminal and at least one second video telephone terminal in a telephone network, a service center is adapted to connect with the first and second terminals over the telephone network. A telephone call is first set up between the first terminal and the second terminal in order to exchange availability signals between the terminals to seek availability to hold a video telephone call therebetween. If such availability is confirmed, the telephone call between the first and second terminals is released, and telephone calls are established between the service center and the first and second terminals, whereby the first and second terminals are connected to one another over the telephone network via the service center. A video telephone call is then set up between the first and the second terminals via the service center.