The subject matter described herein includes methods, systems, and computer readable media for providing foreign routing address information to a telecommunications network gateway. According to one aspect, the method includes, at a call signaling message routing node in a first telecommunications network, intercepting a call setup message that includes a called party number identifier and is directed towards a network gateway connected to at least one foreign telecommunications network. The method also includes accessing a foreign routing information database using an ENUM formatted query message to obtain foreign routing address information associated with the at least one foreign telecommunications network, modifying the call setup message to include the address information, and routing the modified call setup message towards the network gateway.