Vilniaus kenesa buvo pradėta statyti 1911 m., 1911 m. spalio 30 d. buvo pašventintas kertinis akmuo. Architektas Michailas Prozorovas. Per dvejus metus iškilo sienos ir buvo uždengtas stogas, tačiau prasidėjus Pirmajam pasauliniam karui, kenesos statybos darbai buvo nutraukti. Kenesos statyba buvo atnaujinta 1921 m. ir 1923 m. rugsėjo 9 d. Vilniaus kenesa buvo pašventinta. Sovietų okupacijos metu 1949 m. ji buvo uždaryta, joje įkurtas trestas, vėliau – geodezijos tarnybos archyvas, gyveno žmonės. 1989 m. Vilniaus kenesa buvo grąžinta karaimų bendruomenei. 1993 m. po remonto vėl pašventinta.
Kenesa pastatyta maurišku stiliumi pagal architekto Michailo Prozorovo projektą. Viduje kenesa padalinta į tris dalis: pagrindinę maldų salę vyrams, galeriją moterims ir vidurį. Prie rytų sienos yra mauritaniškas echalas. Vilniaus kenesa – pati naujausia Lietuvos kenesa.
