Teredo fue desarrollado en febrero de 2006 por Christian Huitema en Microsoft y fue normalizado por la IETF en RFC 4380.
Bajo la norma RFC 6081 se establecieron unos complementos para mejorar su eficiencia y compatibilidad con varios tipos de NAT.
Muchos de los dispositivos NAT usados actualmente no pueden ser actualizados para implementar 6to4 por razones técnicas o económicas.
Teredo soluciona este problema encapsulando paquetes IPv6 dentro de datagramas UDP IPv4, los cuales pueden ser reenviados correctamente por NATs.
Un host que implemente Teredo puede tener conectividad IPv6 sin cooperación por parte de la red local o del dispositivo NAT.