We propose a transcoding-enabled caching system (TeC) along with a new set of caching algorithms for video delivery over the Internet. Our system is designed for efficient delivery of rich media web contents to heterogeneous network environments and client capabilities. The proxies perform transcoding as well as caching in our system. This design choice allows content adaptation to be performed at the edges of the networks. Depending on the connection speed and processing capability of an end user, the proxy transcodes the requested (and possibly cached) video into an appropriate format and delivers it to the user. By serving the transcoded video directly from the proxy, we improve the cache hit ratio. Simulation results indicate that by incorporating transcoding capability at the network edges, the traffic to the content origin server is reduced 20%.