It is obvious that customers are essential stakeholders in organizations and their satisfaction is a priority to the management. Satisfying customers by ensuring good quality services is the latest organizational strategy in today's business world. So, service quality nowadays has become ever more important to the achievement of customer satisfaction and competitive advantage as well. This coupled with the mounting complexities of the needs and expectations of customers in general. Prior research has suggested that customers' expectations and perceptions are more likely to be different across service sectors. Additionally, much of the research conducted about this theme has concentrated on the private sector. However, public sector organizations, especially in developing countries, play more dominant roles in service delivery. For that reason, the primary purpose of this study is to examine the relationship between service quality and customer (citizen) satisfaction in public service sectors with respect to service quality dimensions. The paper aims at identifying the determinants of service quality from the customers' perspective, and how they affect their satisfaction. The SERVQUAL tool developed by Parasuraman, et al. (1988) was used with its five dimensions (tangibility, reliability, responsiveness, assurance, and empathy), to find out how applicable it is in the context of the public sector. Empirically, the paper explores the relationship between service quality dimensions and customer satisfaction at EgyptAir. Finally, the research provides useful and beneficial findings and recommendations which can be adopted by public service providers, in an attempt to build up and promote sustainable quality and successful customer satisfaction strategies, particularly in the Egyptian public sector.