The globalization of businesses and the germination of customer satisfaction importance induced a profound transfer from transitional to relational marketing, together with the introduction of relationship marketing concept. To surmount this transition, business process improvement is acknowledged as one of the prevailing methods to conduct changes in organizations. Concerning the achievement of process superiority and the superlative services to customers, practitioners are advised to benefit the customer-oriented BPI methodologies. While they have their roots in private sectors and manufacturing organizations, recently they are widely used in public sectors as well. Since the essential essence of BPI in public sectors is enhancing the satisfaction of customers, the existing approaches mainly focus on cost reduction and policy-based process introduction. Sifting through organizations’ processes, diagnosing befitting tools, and evaluating techniques can be a daunting task. The available literature on business process improvement in public sectors is full with recommendations on how to do improvements and the methodologies, but what is lacking is a customer-oriented BPI guideline together with necessary tools and technologies for each step. Following the mentioned gap, this paper proposes a customer-oriented methodology to conduct process improvement smoothly in public sectors besides the necessary tools and techniques for each phase.