This paper considers a centralized cloud-based multimedia system (CMS) consisting of a resource manager, cluster heads, and server clusters, where the resource manager assigns clients' requests for multimedia service tasks to server clusters, and then each cluster head distributes the assigned task to the servers of its server cluster. It has been a research challenge to design an effective load balancing algorithm for a CMS, which spreads the multimedia service task load on servers with the minimal cost for transmitting multimedia data between server clusters and clients under some constraints. Unlike previous works, this paper takes into account a dynamic multi-service scenario in which each server cluster only handles a specific type of multimedia tasks, and each client requests a different type of multimedia services at different time. Such a scenario can be modelled as an integer linear programming problem, which is computationally intractable in general. Hence, this paper further solves the problem by an efficient genetic algorithm. Simulation results demonstrate that the proposed genetic algorithm can efficiently cope with dynamic multi-service load balancing in CMS.