The application of innovative technologies for advancing mobile workforce management often represents a considerable financial barrier, especially for small and medium enterprises. In this paper, we propose an on-demand and multi-tenancy cloud-based workforce management system utilizing state-of-the-art mobile and non-mobile technologies and vehicle routing methodologies. The prototype includes functionality to manage customer data, track and communicate with mobile workers, and to efficiently plan routes by solving vehicle routing problems with different metaheuristics in a highly scalable cloud environment using the Google App Engine. The cloud-based solution can be flexibly used “as a service” by different organizations and thus enables smaller enterprises to utilize innovative technologies for low variable expenses in order to improve their competitiveness. To the best of our knowledge, the proposed prototype is the first integrative approach to support the management of mobile workforces in the cloud. The generic architecture builds a foundation for implementing cloud-based real-time decision support and communication in other appropriate application areas.