Multimedia computing has attracted considerable attention with the rapid growth in the development and application of multimedia technology. Current studies have attempted to support the increasing resource consumption and computational overhead caused by multimedia computing. In this paper, we propose $MediaCloud$, a new multimedia computing paradigm that integrates the concept of cloud computing in handling multimedia applications and services effectively and efficiently. $MediaCloud$ faces the following key challenges: heterogeneity, scalability, and multimedia Quality of Service (QoS) provisioning. To address the challenges above, first, a layered architecture of $MediaCloud$, which can provide scalable multimedia services, is presented. Then, $MediaCloud$ technologies by which users can access multimedia services from different terminals anytime and anywhere with QoS provisioning are introduced. Finally, $MediaCloud$ implementation and applications are presented, and media retrieval and delivery are adopted as case studies to demonstrate the feasibility of the proposed $MediaCloud$ design.