An approach is disclosed for detecting source network address translation in internet protocol (IP) tunneling flows and using learned source IP addresses and source ports from such detection to create new tunnels. In one embodiment, a NAT detection application determines whether source IP addresses and source ports associated with new traffic flows destined to a local Foo-over-UDP (FOU) tunnel endpoint match the source IP address and source port of a previously configured FOU tunnel. Lack of such a match is indicative of source network address translation, and in such a case the NAT detection application creates a new FOU tunnel toward the detected source IP address and source port. In addition, the NAT detection application authenticates the remote endpoint of the newly created FOU tunnel and configures the FOU tunnel for use if the remote endpoint is successfully authenticated.