Nabokov zaczął rozwijać w formie powieściowej pomysł zawarty w Czarodzieju w 1949 roku. Początkowo książka miała nosić tytuł The Kingdom by the Sea, a jej bohaterka miała się nazywać Juanita Dark, Joan of Ark lub Joaneta Darc jako aluzja do Joanny d’Arc. Imiona te miały być, według sugestii autorskiej, wymawiane z hiszpańska: Huanita, Hoan, Hoaneta. Juanita zmieniła się w Lolitę w 1950 roku.
Utwór nie powstawał w kolejności zgodnej z powieściowymi wydarzeniami – autor rozpoczął pisanie od pierwszej podróży Humberta i Lolity, następnie opisał śmierć Quilty’ego i epizody z przeszłości Humberta, a dopiero później uzupełnił resztę powieści w porządku chronologicznym. Prace nad powieścią posuwały się bardzo wolno. Zniechęcony Nabokov niejednokrotnie chciał zniszczyć szkic utworu. W 1953 roku poświęcał na pisanie powieści 16 godzin dziennie. Prowadził również badania, mające pomóc mu w konstrukcji świata przedstawionego: czytał informacje prasowe na temat pedofilii, jeździł autobusami szkolnymi, aby poznać język młodzieży, odwiedził szkołę i obserwował wygląd koleżanek swojego syna.