For many years, the tight bureaucratic and task centered approaches of civil service institutions of Ethiopia led to fragmentation, overlap and duplications of efforts than being responsive, flexible and customer focus. To this end, Business Process Reengineering (BPR) has been considered as a government sector technique to help organizations fundamentally rethink how they do their work in order to dramatically improve customer service, cut operational costs, become responsive, flexible and customer focus. BPR has great potential for increasing productivity through reduced process time and cost, improved quality, and greater customer satisfaction, but it often requires a fundamental organizational change. Despite the numerous advantages of BPR in terms of responsiveness, flexibility and customer focus, its implementation is perceived to be a difficult task and also many unsuccessful experiences have been reported in the literature. In fact, there are very few survey researches that attempt to highlight the kinds of activities that the organizations should pursue to ensure a reasonable transition to the new process; manage the human and technical issues surrounding implementation of the new process; and assess the results of its reengineering efforts. But these researchers saw the issues from private cooperative organizational perspectives and contexts. Besides, most of the discussions and findings were stretched up to showing that successful BPR implementations process are mainly associated with the organizations capability in managing changes. The researches paid no attention to other factors, like the issues of enabler, tools and techniques which can be utilized to build momentum. Hence, the present research investigated the factors associated with successful implementations of BPR projects in the contexts of public institutions. Based on a case study conducted in Ethiopian Ministry of Health and Gambella Regional Health Bureau; this research attempted to provide guidelines and best practices in public service providing institutions that will help them to achieve dramatic performance gains while implementing BPR projects. A cross sectional, qualitative and quantitative study was conducted taking 90 respondents and 20 interviewees as study subjects. Data were collected from June 1 to July 31 2010. A structured questionnaire was filled by 90 respondents where 43.3 % of them from Gambella Peoples’ National Regional State Health Bureau and 56.7% of them were from Ethiopian Federal Ministry of Health. The questionnaire was employed to collect data on change management and factors associated with the attainment of performance goals whereas in-depth interviews were utilized to substantiate the findings of questionnaire and investigate the use of information technology as enabler. The in-depth interviews included planners, core process owners and directors. Cross tabulation results imply that there is significant associations between attainment of performance goals and availability of written comprehensive plan for pilot test, refinement and implementation of change management plan, availability of communication strategy, placement of performance measures, motivation to take new roles and responsibilities, Use of information technology as enabler and pilot testing to evaluate new process. Hence, the findings of this research suggest that reengineering project implementation is complex, involving many factors. To succeed, it is essential that change be managed and that balanced attention be paid to all identified factors, including those that are more contextual (e.g., management support and technological competence), performance management, availability of comprehensive implementation plan, communication strategies, refinement and implementation of change management plan, use of pilot testing to evaluate new process, motivation to take new roles and responsibilities and usage information technology as enabler.