Government agencies are increasingly making use of cloud computing (CC) services, initially simpler infrastructure and platform as a service (IaaS and PaaS) ones, and later more sophisticated software as a service (SaaS) ones. However, with respect to the latter the electronic support of the high complexity government processes is a difficult task and requires highly sophisticated and complex government-specific SaaS offering extensive functionalities for fulfilling the extensive requirements posed by relevant legislation. It is therefore imperative to conduct comprehensive evaluations of such complex government-specific SaaS, in order to assess to what extent they support the targeted government processes and fulfil their extensive and complex requirements, and also identify and prioritize necessary improvements. This paper presents an advanced methodology for evaluating complex government-specific SaaS, which enables comprehensive multi-dimensional evaluation of a wide range of aspects of them that are highly important in the government context, and detailed evaluation of the provided complex and extensive functionality with respect to the requirements defined by relevant legislation; furthermore, it enables a rational identification and prioritization of necessary improvements. It is based on the estimation of multi-layer ‘value flow models’ of these SaaS from evaluation data collected from users. The proposed methodology has been applied for the evaluation of a complex SaaS aiming to support the wide range of activities of the Greek ‘Local School Committees’, which are responsible for managing all government funding provided for the operation of all the schools in a specific geographical area, as well as all other income of them, and for covering all kinds of their operating expenses as well as purchases. The research presented in this paper can contribute to a more rational, efficient and effective exploitation of an emerging ‘disruptive technology’, the CC, and especially its most sophisticated form, the SaaS, in the public sector.