Enhancing teamwork performance is a significant issue in mobile cloud-based learning. We introduce a service oriented system, Teamwork as a Service (TaaS), to realize a new approach for enhancing teamwork performance in the mobile cloud environment. To coordinate most learners’ talents and give them more motivation, an appropriate task allocation is necessary. Utilizing the Kolb’s learning style (KLS) to refine learner’s capabilities, and combining their preferences and tasks’ difficulties, we formally describe this problem as a constraint optimization model. Two heuristic algorithms, namely genetic algorithm (GA) and simulated annealing (SA), are employed to tackle the teamwork-enhanced task allocation, and their performances are compared respectively. Having faster running speed, the SA is recommended to be adopted in the real implementation of TaaS and future development.