A telephone number change notification method is provided in which a calling party is reliably identified when a new telephone number of a called party is notified to the calling party when the called party changed the telephone number. When a telephone exchange detects that a called number is changed based on a subscriber information database, the telephone exchange sends a prompt message asking for sending a telephone number notification request to a calling telephone. The calling telephone creates a digital signature and sends it to the telephone exchange. The telephone exchange forwards it to a new telephone number of a called telephone. The called telephone receives the digital signature and verifies it. If the digital signature is valid, the called telephone notifies a new telephone number to the calling telephone.