Meie ajalugu läheb tagasi 19. sajandisse, mil Johann Heinrich Brasche eestvedamisel saadi Tallinna linnalt maja Liivalai tänavale, kus 1880. aastal avati Väikeste Laste Hoid. Väiksematel möödus aeg põhiliselt mängides, aga suurematele toimusid ka koolitunnid: piiblilugu, matemaatika, saksa keel, venekeel, käsitöö. Suurt rõhku pöörati muusikale. Selts töötas 60 aastat, kuni „vabastajad“ selle sulgesid.
1918. aastal kutsuti ellu Kaarli Eragümnaasium, kus väärtustatud olid kristlik kasvatus ja üldhumaansed põhimõtted. Seegi kool sai tegutseda kuni 1936. aastani.
Kaarli Koguduse Lasteaia tegutsemise alguseks on 1995. aasta, mil koguduse juurde loodi kolm korda nädalas koos käinud kooliks ettevalmistuv rühm. Alguses oligi suund algkooliks kasvamisel, aga järgmisest aastast alustati koguduse majas hoopis traditsioonilise lasteaiana. Esialgu ühe-, õige pea aga kahe-rühmalisena. 1998. aastast on lasteaial Eesti Vabariigi Haridusministeeriumi koolitusluba.
Kuna aga kristlikku kasvatust väärtustavaid lapsevanemaid oli ikka ja alati rohkem, kui lasteaial võimalik vastu võtta, hakkasime laienemise plaani pidama. Tänu eestvedajate entusiasmile ja suurele panustamisele sai nii mõnelegi vaid ilusa unistusena näiv idee siiski teoks ja 2008. aasta augustis õnnistati lasteaia uued ruumid Koidu tänaval, mille remontimisel ja lasteaia tarbeks ümberkohendamisel lõid käed külge nii elukutselised ehitajad, koguduse liikmed, lapsevanemad kui ka Kaarlikese sõbrad ja head tuttavad. 2009. aasta sügisel avati lisaks ka sõimerühm, sellest alates töötab lasteaed viie rühmaga, 1,5 – 7 aastastele lastele.
Lasteaia taustal toimus aastaid pidev keskustelu sarnase keskkonna jätkumiseks kooli-astmetes. Eelkõige on selle huvi algatajateks meie lapsevanemad, kes soovisid oma laste haridustee jätkumist samas tervikus koguduse ja ka lasteaiaga. Ka pedagoogid leidsid, et selline areng oleks väga oluline, et kristlike väärtuste ja teadmiste edastamine oleks järjepidev ja kannaks vilja.
2013. aasta juunis andis Haridus- ja Teadusministeerium välja koolitusloa Kaarli Koolile, mis nüüdsest hõlmab nii lasteaeda, põhikooli kui gümnaasiumi.
Kool töötab ühe klassiga igas vanuserühmas, klasside suuruseks on keskmiselt 20 õpilast, gümnaasiumis 25 õpilast.