Recent advances in mobile devices and network technologies have set new trends in the way we use computers and access networks. Cloud Computing, where processing and storage resources are residing on the network is one of these trends. The other is Mobile Computing, where mobile devices such as smartphones and tablets are believed to replace personal computers by combining network connectivity, mobility, and software functionality. In the future, these devices are expected to seamlessly switch between different network providers using vertical handover mechanisms in order to maintain network connectivity at all times. This will enable mobile devices to access Cloud Services without interruption as users move around. Using current service delivery models, mobile devices moving from one geographical location to another will keep accessing those services from the local Cloud of their previous network, which might lead to moving a large volume of data over the Internet backbone over long distances. This scenario highlights the fact that user mobility will result in more congestion on the Internet. This will degrade the Quality of Service and by extension, the Quality of Experience offered by the services in the Cloud and especially multimedia services that have very tight temporal constraints in terms of bandwidth and jitter. We believe that a different approach is required to manage resources more efficiently, while improving the Quality of Service and Quality of Experience of mobile media services. This paper introduces a novel concept of Cloud-Based Mobile Media Service Delivery in which services run on localized public Clouds and are capable of populating other public Clouds in different geographical locations depending on service demands and network status. Using an analytical framework, this paper argues that as the demand for specific services increases in a location, it might be more efficient to move those services closer to that location. This will prevent th- Internet backbone from experiencing high traffic loads due to multimedia streams and will offer service providers an automated resource allocation and management mechanism for their services.