In this paper we provide an evaluation and certification approach for Voting Service Providers (VSPs) which combines the evaluation of the electronic voting system and the operational environment for the first time. The VSP is a qualified institution which combines a secure voting system and a secure operational environment to provide secure remote electronic elections as a service [La08]. This centralized approach facilitates legal regulation and evaluation. So far, a legal regulation framework for VSPs has been developed which demands evaluation and certification of the VSP [Sc09a]. Therefore the VSP is required to provide a security concept in which it demonstrates satisfaction of the security requirements defined in the legal regulation. However neither the content of this security concept nor an adequate evaluation methodology has been specified so far. We therefore developed a security concept template and a comprehensive evaluation methodology for the VSP, which includes both the voting system and operational environment of VSPs. Our proposal incorporates existing evaluation methodologies to facilitate evaluation and certific ... mehration. With this paper and the legal regulation a realistic approach to enable the VSP concept is accomplished.