Mokykla savo veiklą pradėjo 1993 m. rugsėjo 1 d. Ji vadinosi Vilniaus 12-oji pradinė mokykla. Mokykla įsikūrusi Medeinos gatvėje, todėl 1994 m. jai suteiktas Medeinos vardas. Tais pačiais metais ji buvo pašventinta.
Nuo pat pirmųjų mokslo metų mokykla teikė pradinio ugdymo ir pradinio specialiojo ugdymo paslaugas. Mokiniai turėjo galimybę mokytis pagilinto anglų kalbos kurso. Tuo metu buvo suformuota 16 klasių. Viena iš jų – pradinio specialaus ugdymo klasė. Iš viso mokykloje mokėsi 362 mokiniai. Mokykla dirbo dviem pamainomis.
Nuo 1997 m. rugsėjo 1 d. buvo įsteigta antroji pradinio specialaus ugdymo klasė. Nuo 2004-2005 mokslo metų mokykloje visi mokiniai mokėsi pirmoje pamainoje.
Mokykloje nuo pat jos įkūrimo pradžios buvo kuriami bendradarbiavimu, pagalba vieni kitiems grįsti mokyklos bendruomenės narių tarpusavio santykiai, nes mokyklos ir šeimos bendradarbiavimas ypatingai svarbus mokinių pasiekimams. Kai vaikas jaučia tėvų bei mokytojų rūpestį, pagalbą, formuojasi teigiama nuostata mokytojų, mokyklos atžvilgiu. Tai didina galimybes patirti sėkmę mokykloje, ugdytis geresnius akademinius, socialinius pasiekimus.
Nuo pat mokyklos įkūrimo pradžios iki šių dienų mokykla žengia tobulėjimo keliu. Pedagogai kelia kvalifikaciją, tobulina dalykines ir bendrąsias kompetencijas įvairiuose seminaruose, konferencijose, išbando pedagogines inovacijas, metodines priemones, naujų vadovėlių komplektus, tikslingai taiko IT ugdymo procese, dalyvauja Vilniaus m. savivaldybės, ESF ir Erasmus projektuose, rengia seminarus, dalijasi gerąja praktine patirtimi pradinio ir specialiojo pradinio ugdymo temomis, sėkmės istorijomis su mokyklos, Lietuvos ir užsienio šalių kolegomis. Mokykla aktyviai bendradarbiauja su universitetais. VDU Švietimo akademijos, VU, Vilniaus kolegijos studentai turi galimybę įgyti praktinių pedagoginio darbo įgūdžių atlikdami praktiką Vilniaus Medeinos pradinėje mokykloje, rengdami baigiamuosius darbus.
Mokykla atvira bendravimui, praktinės patirties pasidalijimui. Nuo mokyklos įkūrimo pradžios mokykloje patirtimi dalijosi pedagogai iš įvairių Lietuvos miestų ir miestelių bei užsienio šalių (Suomijos, Švedijos, Prancūzijos, Didžiosios Britanijos, Rusijos, Kazachstano, Moldavijos, Ukrainos, Latvijos, Estijos, Lenkijos, Gruzijos (Sakartvelo), Kirgizijos, Armėnijos ir kt.).
2019 m. vasarį mokykloje buvo surengta teorinė-praktinė konferencija „Kiekvieno mokinio asmeninė pažanga–sėkminga mokykla“, skirta mokyklos veiklos 25-mečiui paminėti. Per šiuos veiklos metus mokykloje kūrėsi savitos tradicijos, įstaigos bendruomenė telkėsi naujiems iššūkiams, kaupėsi geroji mokymo ir mokymosi patirtis. Aktualu ir prasminga pasidalyti idėjomis, ateities įžvalgomis, juk pasak Leonido Donskio „Švietimas yra sugebėjimas nesustoti, nes sustojimas šiame pasaulyje, kuris nestovi, reikštų ėjimą atgal. Mokykla nėra žinios ar informacija, tai ėjimas į priekį.“
