Certifying the execution of a service is a critical issue for an e-government infrastructure. In fact being able to document that an e-service was actually carried out, given the legal value that is often attached to data managed and exchanged by public administrations, is of the utmost importance. This is made more complex in cases, like it often happens in the public administration sector, where e-services are based on legacy systems managed by autonomous and independent organizations. In this paper we discuss the introduction, within the standard three tier architecture for e-services, of an architectural subsystem providing certification functions. This architecture features both physical and functional independence from the application level and is made up by new control components providing a highly efficient solution for certification requirements. Our solution has been successfully tested in real-world systems developed in Italy to support digital government functions.