In this paper, we address the problem of cache replacement for transcoding proxy caching. Transcoding proxy is a proxy that has the functionality of transcoding a multimedia object into an appropriate format or resolution for each client. We first propose an effective cache replacement algorithm for transcoding proxy. In general, when a new object is to be cached, cache replacement algorithms evict some of the cached objects with the least profit to accommodate the new object. Our algorithm takes into account of the inter-relationships among different versions of the same multimedia object, and selects the versions to replace according to their aggregate profit which usually differs from simple summation of their individual profits as assumed in the existing algorithms. It also considers cache consistency, which is not considered in the existing algorithms. We then present a complexity analysis to show the efficiency of our algorithm. Finally, we give extensive simulation results to compare the performance of our algorithm with some existing algorithms. The results show that our algorithm outperforms others in terms of various performance metrics.