Kuressaare Põhikool oli Kingissepa 8-klassilise Kooli õigusjärglane, mis alustas õppetööd 1. septembril 1960. Hiljem kandis kool nime Kuressaare 9-klassiline Kool ja alates 1992. aastast Kuressaare Põhikool.
Ruumikitsikuse, aga ka ühiskondlike olude sunnil kolis Kingissepa 8-klassiline Kool 1978. aastal märksa suuremasse koolihoonesse aadressil Garnisoni tänav 16.
Aadressil Garnisoni tänav 16 on ajalooliselt asunud isegi kolm koolimaja. Vanim neist (mantelkorstnaga koolihoone Garnisoni ja Rootsi tänavate ristmikul) lammutati 1965. aastal. Teises, 18. sajandil rajatud kelpkatusega hoones (tänapäeval aadressil Garnisoni tänav 16a) asus aastatel 1805–1914 poeglaste elementaarkool, mille juhataja oli 19. sajandi viimasel veerandil Johannes Reutz. „Reutzi koolis” õppisid teiste seas näiteks Johannes Aavik ja Oskar Kallas. 20. sajandi esimesel aastakümnel oli kooli juhataja tuntud muusikategelane Karl Linnamägi. 1939. aastal ehitati selle väikese vana koolimaja kõrvale linnaarhitekt Eugen Haameri projekti järgi uus, funktsionalistlikus stiilis algkoolihoone. Ehitusinsener oli Armin Talk. Avamise puhul kinkis Eugen Haameri vend maalikunstnik Eerik Haamer koolile oma teose "Saaremaa", mis asub tänapäeval Saaremaa Muuseumis.[2]
1965. aastal tehti Eugen Haameri kavandatud hoonele aadressil Garnisoni tänav 16 juurdeehitus. Sellega lisandus olemasolevale üheksale suurele klassiruumile veel kuus suurt klassiruumi ja koolihoonet sai kasutada 8-klassilise kooli õppetööks.[2]
