Development was started end of November 1998. The package was called rssh.el, back then. It only provided one method to access a file, using ssh to log in to a remote host and using scp to transfer the file contents. After a while, the name was changed to rcp.el, and now it's tramp. Along the way, many more methods for getting a remote shell and for transferring the file contents were added. Support for VC was added.
After that, there were added the multi-hop methods in April 2000 and the unification of tramp and Ange-FTP file names in July 2002. In July 2004, multi-hop methods have been replaced by proxy hosts. Running commands on remote hosts was introduced in December 2005. Support of gateways exists since April 2007. GVFS integration started in February 2009. Remote commands on Windows hosts are available since September 2011. Ad-hoc multi-hop methods (with a changed syntax) have been reenabled in November 2011. In November 2012, Juergen Hoetzel's tramp-adb.el has been added.
In December 2001, tramp has been added to the XEmacs package repository. Being part of the Emacs repository happened in June 2002, the first release including tramp was Emacs 22.1.
tramp is also a Debian GNU/Linux package since February 2001.