A system and method for providing fault tolerance in a network telephony system. Signaling messages according to a signaling protocol, such as the SIP protocol, are modified to include a path attribute with a network address corresponding to a backup proxy server. When a primary proxy server is supported by a backup proxy server, the primary proxy server inserts the Alternate Path tag into one or more signaling messages. When a network entity sends a message, it checks the message to identify the primary proxy server. Upon receiving a failure or timeout when attempting to send to the primary proxy server, the sending network entity should try the backup proxy server specified in the path attribute. When the backup proxy server receives the message, it may modify the message to specify the new routing path. As a result, subsequent messages get routed properly using the backup proxy server.