Mokykla įkurta 1988 m. rugsėjo 1 d.
2004 m. vasario 11 d. mokyklos bendruomenės prašymu Vilniaus 60-ajai vidurinei mokyklai suteiktas Aleksandro Puškino vardas. 1988–2008 m. mokyklai vadovavo Nina Gavriušina. Nuo 2008 m. iki 2023 metų mokyklai vadovavo Jelena Žurovska. Nuo 2024 metų mokyklos direktoriumi paskirtas Aleksej Peržu.
Mokykla tęsia Vilniaus Aleksandro Puškino gimnazijos, veikusios Vilniuje iki 1940 m., kultūrines tradicijas. Mokyklos prioritetas – siekti Geros mokyklos koncepcijos bei glaudžiai bendradarbiaujant bendruomenei puoselėti rusų bendruomenės Lietuvoje dvasines ir etnokultūros vertybes, kartu teikiant aukštos kokybės ugdymą.
Mokykloje dirba aukštos kvalifikacijos mokytojai. Jie taiko pačius efektyviausius mokymo metodus, naudoja šiuolaikines technologijas. Mokyklos darbuotojų atsakomybė ir jų profesionalumas lemia mokinių pažangą, kasmet siekiančią apie 99,08 proc. Pažymėtina, kad 2014–2015 m. m. laidos abiturientai tris kartus gavo 100 balų brandos egzaminų aukščiausią įvertinimą. Mokyklos mokiniai aktyviai dalyvauja miesto ir respublikos olimpiadose, konkursuose, pelno apdovanojimus. Mokyklą baigę abiturientai sėkmingai tęsia mokslus aukštosiose Lietuvos, Didžiosios Britanijos, Danijos, Norvegijos, Vokietijos, Prancūzijos, JAV mokymosi įstaigose.
Vilniaus Aleksandro Puškino mokykloje rusų mokomąja kalba vykdomas ugdymas neatsiejamas nuo visų mokykloje besimokančių moksleivių integracijos į Lietuvos kultūrą ir gyvenimą programos įgyvendinimo. Mokykloje mokosi daugiau kaip 700 įvairių tautybių mokinių: rusų, lietuvių, žydų, gruzinų, baltarusių, lenkų, ukrainiečių, vietnamiečių, azerbaidžaniečių, čečėnų, kazachų ir kt. NMVA išvadose teigiama, kad mokykloje skiriamas ypatingas, išskirtinis dėmesys kiekvieno vaiko raidai (NMVA išvados): gabūs ir talentingi 2–3 kl. mokiniai apdovanojami „Sidabrinės pelėdos“ nominacija, 4–5 kl. mokiniai nominuojami „Auksinės žuvelės“, 7–10 kl. mokiniai suburiami bendrai veiklai gabių ir talentingų mokinių klube „Everestas“ bei apdovanojami klubo diplomu. Siekiant tinkamai paruošti būsimus pirmokus mokyklai kasmet organizuojama sekmadieninė mokyklėlė „Vaivorykštė“.
Mokykloje daug dėmesio skiriama rusų kultūros istorinio paveldo Lietuvoje, stačiatikių krikščioniškosioms vertybėms puoselėti. Siekiant puoselėti savo tautos etnokultūrinį tapatumą, šios veiklos kryptys integruojamos į mokyklos formalųjį ir neformalųjį ugdymą.
Mokykla siekia tapti savitą ugdymo sistemą taikančia mokykla. Tuo tikslu buvo parengta Humanistinės kultūros ugdymo menine veikla sampratos elementų taikymo programa, kurios tikslas – atskleidžiant mokinių kūrybingumą, puoselėjant jų meninius gebėjimus, ugdyti ir formuoti mokinių humanistinės kultūros vertybines nuostatas, būtinas asmens saviraidai tolesniame gyvenime.Šios programos elementai nuo 2015 m. yra integruojami į ugdymo procesą.
1989 m. mokykloje įkurtas Aleksandro Puškino muziejus, kuris 2008 m. buvo įtrauktas į Lietuvos Respublikos muziejų katalogą. Muziejaus sukaupta medžiaga naudojasi ne tik mokyklos bendruomenė, bet ir kitos Vilniaus miesto mokyklos.
Mokykla išsiskiria savo kultūra, sukurtomis tradicijomis, ritualais, atvirumu bei svetingumu, palankiu mikroklimatu, sėkmingu ir aktyviu dalyvavimu olimpiadose ir konkursuose. Mokykla domisi mokinių pasiekimais, nuolat juos stebi, analizuoja ir siekia, kad būtų geresni. Nuolat analizuojama bei tobulinama mokyklos mokinių vertinimo sistema, tikslinga konsultavimo ir kuravimo sistema.
Nuolatinį dėmesį mokykla skiria gerai mokinių savijautai mokykloje užtikrinti. Mokyklos veikla grindžiama bendruomenės narių pagarbiu bendravimu ir bendradarbiavimu. Remiantis STA duomenimis, 88, 0 proc. tyrime dalyvavusių tėvų patenkinti, kad jų vaikai mokosi šioje mokykloje, o 97, 7 proc. tyrime dalyvavusių mokinių didžiuojasi, jog čia mokosi.
Mokykloje puoselėjamos tradicijos organizuoti šventes, pilietines akcijas, tokias kaip „Licėjaus diena“, Aleksandro Puškino gimimo ir tragiškos žūties metinių minėjimas; stačiatikių kultūros forumas „Kalėdiniai susitikimai“, slavų raštijos pradininkų šv. Kirilo ir Metodijaus pagerbimas, apeiginės šventės Užgavėnės („Maslenica“), Tarpukalėdis („Sviatki“), iškilmingas koncertas Motinos dienai paminėti, „XIX a. tradicinis pokylis“, „Atmintis gyva, nes liudija“, „Darom“, „Donoro diena“, „Dalinkimės gerumu“, „Mąstau. Rūšiuoju. Gyvuoju“, „Pasakyk diskriminacijai NE“ ir kt. Taip pat mokiniai talkina A. Puškino literatūrinio muziejaus Markučiuose, Pašilaičių mikrorajono organizuojamoje visuomeninėje veikloje.
Mokykla dalyvauja mainų programoje „ERASMUS +“. Dalyvavimas programoje, bendravimas ir bendradarbiavimas su kitų šalių mokiniais atveria kelią naujoms patirtims, naujoms žinioms, perspektyvoms, skatina jausti pagarbą ir toleranciją skirtingos tautos, rasės, lyties, religijos, tautybės žmonėms, taip pat ugdo atvirumą kitoms kultūroms, idėjoms, atsakingumą ir pilietiškumą.
Nuolat plečiamas socialinių partnerių tinklas. Mokykla bendrauja ir bendradarbiauja su Lietuvos bei užsienio aukštosiomis ir profesinio mokymo mokyklomis, taip pat su kitomis mokslo įstaigomis.
Bendruomenės pastangomis sėkmingai naujinama ir gerinama ugdymo(si) aplinka, atitinkanti aprūpinimo šiuolaikinėmis techninėmis priemonėmis reikalavimus.
Vilniaus m. savivaldybės tarybos 2017 m. rugpjūčio 16 d. sprendimu Nr. 1-1082 „Dėl Tarybos 2016-03-23 sprendimo Nr. 1-369 „Dėl Vilniaus miesto savivaldybės bendrojo ugdymo mokyklų tinklo pertvarkos 2016-2020 metų bendrojo plano tvirtinimo“ pakeitimo“ nutarta Vilniaus Aleksandro Puškino mokyklą pertvarkyti į gimnaziją, taikančią savitos ugdymo sistemos elementus.
2018 metų birželio mėn. LR Švietimo ir mokslo ministerijos rašte „Dėl Vilniaus Aleksandro Puškino ir Vilniaus Fabijoniškių mokyklų“ teigiama, kad Švietimo ir mokslo ministerija, vykdydama Ministro Pirmininko pavedimą, įformintą Vyriausybės kanclerio 2018 m. balandžio 19 d. rezoliucija Nr. S-1253, neprieštarauja, kad nuo 2018 m. rugsėjo 1 d. būtų sudarytos III (–trys) gimnazijos klasės.