Proxy servers play an important role in between servers and clients in various multimedia systems on the Internet. Since proxy servers do not have an infinite-capacity cache for keeping all the continuous media data, the challenge for the replacement policy is to determine which streams should be cached or removed from the proxy server. In this paper, a new proxy replacement algorithm, named the Least Popular Used (LPU) caching algorithm, is proposed for layered encoded multimedia streams in the Internet. The LPU method takes both the short-term and long-term popularity of the video into account in determining the replacement policy. Simulation evaluation shows that our proposed scheme achieves better results than some existing methods in term of the cache efficiency and replacement frequency under both static and dynamic access environments.