Cloud-based multimedia application has emerged as a popular service, delivering on demand media computing and storage to millions of users. Though widely deployed, the quality of service (QoS) in current cloud-based multimedia service is not satisfying, due to the varying user demands and strict response time requirements. This thesis investigates resource allocation approaches to improve QoS for cloud-based multimedia services. A service model is desired to quantify the user demands and resource allocation. To meet this need, we propose a queueing model to characterize the cloud service process, based on which we investigate the response time minimization problem and the resource cost minimization problem in single-service scenario, multi-service scenario, and priority service scenario, respectively. Dynamic workload causes the unbalanced resource utilization and local congestion in multimedia cloud. To address this issue, we propose a two-time-scale resource configuration (TRC) scheme to dynamically allocate virtual machines (VMs) to adapt to varying workload. Based on the TRC scheme, we solve the optimal VM configuration problems to minimize the resource cost or minimize the average response time for the single-site cloud scenario and the multi-site cloud scenario, respectively. We propose optimal workload scheduling schemes at user level and task level, respectively. At user level, we optimize the workload assignment to minimize the response time or minimize the resource cost. At task level, we introduce a directed acyclic graph to model the precedence constraints among tasks, and then solve the execution time minimization problems for sequential structure, parallel structure, and mixed structure, respectively. Cloud gaming is an emerging interactive multimedia service. However, current cloud gaming suffers from a high bandwidth consumption and a large response delay. We propose a hybrid streaming framework to provide a high quality cloud gaming experience. We solve the delay-rate-distortion (d-R-D) optimization problem to minimize the overall distortion under the bandwidth and response delay constraints.