The successful deployment and exploitation of an Information and Communications Technologies (ICT) project in a traditional Public Organization involves the proper design and implementation of the Information System (IS) and a proper combination of Business Process Re-engineering (BPR) and Change Management (CM) techniques, specially adapted to meet the organizations' needs. The current work describes the transformation of such an organization, the Holy Archdiocese of Athens, earlier functioning based on a bureaucratic model, into a modern organization, integrating Information Technology (IT) in core processes and offering electronic public services to citizens. Over and above IT expertise, an individual approach of BPR and CM techniques were used in order to meet the challenges set by the nature of this project, the outdated processes in a church organization and the problems caused by elder, unfamiliar with IT and highly resistant to change personnel.