E-Government basically comprises the use of electronic communications technologies such as the internet, in enhancing and advancing the citizens access to public services. In most developing countries including Burundi, citizens are facing many difficulties for accessing public services. One of the identified problems is the poor quality of service in managing citizens’ complaints. This study proposes an SMS and web based e-Government Model as a solution. In this study, a case study of a complaint management system at District of Gihosha has been used as a reference to prove that SMS and Web based e-Government Model can enhances the access of public services. The objective of this study is the development of an SMS and web-based system that can enhances the process and the management of citizens’ complaints at District of Gihosha. The system has been developed using PHP as front end, Apache as web server, MySQL as Database and Gammu as SMS gateway. The obtained results after testing the system shows that all the functionalities of the developed system worked properly. Thus, the SMS and web based complaint management system developed is considered to be effective.