A communication terminal device includes a connection establishing unit which establishes a connection by a call control protocol with a destination device designated by an IP telephone number, a communication protocol requesting unit which request a presentation of a plurality of communication protocols which can be supported by the destination device over the connection, a communication protocol selecting unit which selects one communication protocol which the communication terminal device itself can support from the communication protocols presented from the destination device as a response to the request by the communication protocol requesting unit, and a communication unit which communicates with the destination device over the connection by the communication protocol selected by the communication protocol selecting unit.