Syyskuussa 2004 viisi nuorta muusikkoa perustivat sessiobändin. He soittivat ensimmäisen livensä 18. päivä marraskuuta Takadanobaba AREAlla ja ennen vuoden loppua he ehtivät soittaa kolme konserttia lisää samaisessa paikassa. Vielä joulukuussa he julkaisivat ensimmäisen levynsä nimellä otanoshimi enban, joka sai jatkoa jo helmikuussa. Molemmat julkaisut olivat saatavilla vain Takadanobaba AREAn konserttien aikana.
Ensimmäisten kuukausien aikana yhtye oli virallisesti pelkkä studioprojekti, mutta saatuaan yleisöltä lämpimän vastaanoton, Sou, Yu≠ki, Megumi, Ryosuke ja BAN päättivät jatkaa täyspäiväisesti yhdessä. Lolita23q:n ensimmäinen livekonsertti virallisen aloituksen jälkeen oli 1. päivä maaliskuuta - missä muuallakaan kuin Takadanobaba AREAlla. Myöhemmin samassa kuussa he osallistuivat tapahtumaan joka järjestettiin Hysteric Media Zone 6 julkaisun kunniaksi. Levyllä ei pelkästään ollut kaksi yhtyeen kappaletta, kokoelman mukana julkaistiin myös ilmainen DVD joka sisälsi heidän ensimmäisen PV:nsä.
21. kesäkuuta yhtye julkaisi ensimmäisen maxi-singlensä, joka myytiin loppuun ja saavutti 9. sijan Oriconin indies-listalla. Samana päivänä toista levyä, tandeki me:Low:ta levitettiin ilmaiseksi SHOXX-lehden kylkiäisenä. Vielä samassa kuussa Lolita23q lähti yhteiskiertueelle Sorobanin kanssa, joka päättyi two-man konserttiin.
Tämän jälkeen seurasi lisää konsertteja, heidän esikoissinglensä toinen painos sekä, viimein, 25. päivä elokuuta yhtyeen ensimmäinnen one-man konsertti. Liven aikana jaettiin Lolitan ilmaista at random katashikaku -DVD:tä. Valitettavasti kaikki ei ollut niin täydellistä miltä päältä päin saattoi näyttää; samana päivänä Megumi jätti virallisesti yhtyeen.
Melko pian yhtye löysi korvaajan poistuneelle kitaristilleen ja kaksi kuukautta myöhemmin he julkaisivat blue city centre -trilogiansa ensimmäisen levyn, joka oli jo ehditty nauhoittaa heidän uuden jäsenensä Ryuuton kanssa.
Nopea esiintymis- ja julkaisutahti vaikutti Soun terveyteen - joulukuun puolessa välissä hän joutui yllättäen sairaalaan. Konserttia, joka oli määrä pitää samana iltana, ei peruttu, vaan Ryosuke korvasi puuttuvan vokalistin paikan. Sou kotiutettiin kaksi päivää myöhemmin ja hän - kuvainnollisesti puhuen - lähti sairaalaovesta suoraan keikkapaikalle. Ei lepoa näille pojille!
Helmikuussa julkaistiin murasaki no yume - kokoelma neljästä vanhemmasta kappaleesta, kahdesta PV:stä sekä bonusraidasta ('vonustruck', kuten he itse sen mielivät kirjoittaa). 1. päivä maaliskuuta he järjestivät konsertin juhlistaakseen ensimmäisen virallisen Liquidroom Ebisu-keikkansa vuosipäivää. Tapahtuma myytiin loppuun.
19. toukokuuta oli seuraavan esiintymisen vuoro. Sinä iltana jaettiin erityistä levyä jota voisi kutsua erityisversion ennakkojulkaisuksi, sillä viisi päivää myöhemmin kauppoihin ilmestyi levy joka sisälsi samaiset kappaleet, joskin hieman eri nimillä. Keikkanauhoitus yhtyeen toukokuisesta one-manista nähtiin Lolitan ensimmäisellä live DVD:llä heinäkuussa 2006, jonka jälkeen ilmestyi vielä uusi minialbumi. Mitäköhän seuraavaksi on luvassa?
