Krilija-järjestö perustettiin 9. lokakuuta 1991. Rekisteröintiä edelsi vuoden kestävä kirjava taistelu eritasoisissa oikeusistuimissa. Media suhtautui järjestön perustamiseen kiinnostuneesti. Järjestö kertoi tavoitteistaan lehdessä, jonka painosmäärä oli 33 miljoonaa. Sen seurauksena saatiin 10 000 yhteydenottoa ympäri maata ja näin saatiin kokoon aktivistien ryhmä. Solvaavia kirjeitä tuli vain 30.
Krilija-järjestö piti myös gay-pride-tapahtuman Pietarissa 27. toukokuuta 2006. Kaupunkilaisten reaktiot olivat positiivisia. Ilmapiiri oli täysin toinen kuin Moskovassa, jossa miliisi ja kansalliset ja uskonnolliset joukkiot hyökkäsivät pride-marssijoiden kimppuun.
Järjestöllä on ollut säännöllisesti keskustelutilaisuuksia. Seuraava pidetään 24. huhtikuuta, ja siinä on teemana mm. Amerikan uusi presidentti. Tämä on järjestyksessä 155. järjestön keskustelutilaisuus.