Methods, systems, and products are provided for tunneling IPv6 packets. Embodiments include receiving, by an origin IPv6 border router from an origin IPv6 host, an IPv6 packet having an IPv6 destination address; receiving, by an origin IPv6 border router from an origin IPv6 host, an IPv4 address for a destination IPv6 border router retrieved from a data structure associating IPv6 destination addresses with IPv4 addresses for destination IPv6 border routers; encapsulating, by the origin IPv6 border router, the IPv6 packet in an IPv4 packet; and sending the encapsulated packet to a destination IPv6 border router at the IPv4 address. In many embodiments, encapsulating, by the origin IPv6 border router, the IPv6 packet in an IPv4 packet is carried out by adding an IPv4 header to the IPv6 packet.