A method of setting up a video telephone call between a first video telephone terminal and a second video telephone terminal on a data network includes the steps of: establishing a telephone call over a telephone network between the first and second terminals; exchanging between the first and second terminals during the telephone call availability signals to seek availability to hold a video telephone call; if the availability is confirmed, releasing the telephone call; establishing respective telephone calls between each of the first and second terminals and a corresponding access server of the data network, for achieving connection of the first and second terminals to the data network; establishing a signalling exchange between the first and second terminals through a service center of the data network to achieve the set up of the video telephone call; and establishing a peer-to-peer video telephone call between the first and second terminals over the data network.