Historia Klub założony został 17 maja 1936 roku przez pracowników Ayuntamiento (ratusza) miasta Gwatemala i stąd nazwa klubu. Do najwyższej ligi Liga Capitalina (liga stołeczna – do momentu utworzenia ogólnonarodowej ligi gwatemalskiej mistrz tej ligi był jednocześnie mistrzem Gwatemali) Municipal awansował w 1938 roku. W swoim debiucie klub zajął drugie miejsce. Municipal aż do dziś nie spadł do niższej ligi, dzięki czemu jest klubem, który gra najdłużej w pierwszej lidze gwatemalskiej bez spadku.
Ogólnonarodową ligę Municipal wygrał w sezonie 1942/43. Z sześciu następnych mistrzostw piłkarze klubu wygrali trzy. Pozostałe wygrał ich największy wtedy rywal – klub Tipografía Nacional Gwatemala. Trenerem klubu Municipal był wtedy Manuel F. Carrera, jeden z założycieli klubu, którego imieniem nazwano stadion używany dziś jako treningowy.
Do roku 1955 najwyższym piłkarzem w historii klubu był napastnik Carlos „Pepino” Toledo, który w ogromnym stopniu przyczynił się do zdobycia przez klub czterech tytułów mistrza kraju (ostatni w sezonie 1954/55 – ostatnim przed zakończeniem kariery). Toledo był pierwszym piłkarzem znanym w całej Gwatemali, podporą reprezentacji narodowej. W swojej karierze zdobył dla Municipal 129 bramek (4. miejsce w historii klubu). Później także był związany z klubem, ale już jako trener.