Multimedia object caching, by which the same multimedia object can be adapted to diverse mobile appliances through the technique of transcoding, is an important technology for improving the scalability of web services, especially in the environment of mobile networks. The performance of multimedia object caching mainly depends on how the objects are selected to be removed for a new object (multimedia object replacement) and where the different versions of a multimedia object are placed (multimedia object placement). In this paper, we address the problem of cache replacement for multimedia object caching. We first propose an optimal solution for this problem. The performance objective is to minimize the total access cost by considering both transmission cost and transcoding cost. The performance of the proposed solution is evaluated with a set of carefully designed simulation experiments for various performance metrics over a wide range of system parameters. The simulation results show that our solution consistently and significantly outperforms comparison solutions in terms of all the performance metrics considered.