Nabokov admitió que Lolita fue la novela más desafiante de escribir. El escritor solía describir la creación de Lolita como "un parto doloroso, un bebé difícil" y el libro en sí como una "bomba de relojería", ya que sabía que provocaría una gran controversia. Era plenamente consciente de que debía tratar el manuscrito con gran cuidado, por lo que lo dejó sin firma y lo entregó en secreto a los editores solo en mano (según las leyes de Comstock era ilegal enviar material erótico a través del correo estadounidense). Aunque se le recomendó que sacara a Lolita de forma anónima debido a su tema controvertido de pedofilia, decidió firmar Lolita con su nombre. Inicialmente, consideró publicar la novela bajo el pseudónimo de Humbert Humbert o un nombre femenino anagramático falso: Vivian Darkbloom.

Primera edición de Lolita en París

Después de las advertencias y rechazos que recibió el autor en EEUU, Doussia Ergaz (el agente de Nabokov) lo ayudó a comunicarse con Maurice Girodias, el fundador de Olympia Press. El autor sabía que Olympia Press, la editorial con sede en París, había estado distribuyendo libros no permitidos en el mundo de habla inglesa. Sin embargo, no sabía que Olympia Press era conocido principalmente por la publicación de pornografía y rápidamente firmó un contrato con Girodias para la edición de Lolita. En septiembre de 1955 se publicó en Francia el libro escrito en inglés; Nabokov recibió las primeras copias de Lolita el 8 de octubre de 1955.

Inicialmente, Lolita no fue revisada por revistas importantes, ya que fue publicada por una pequeña editorial en aproximadamente 5,000 copias. No fue hasta finales de 1955 cuando Graham Greene en The Sunday Times de Londres calificó el libro de Nabokov como una de las tres mejores novelas del año. Visitantes de una librería de Londres ojeando los libros recién publicados de "Lolita", 1959

La polémica de los censores, las prohibiciones y los temas escandalosos crearon mucho entusiasmo alrededor de la novela. La gran controversia centrada en Lolita de Nabokov generó una demanda creciente para el libro en los Estados Unidos, donde se publicó finalmente el 18 de agosto de 1958 por los Hijos de G. P. Putnam. En Gran Bretaña, Lolita fue publicada por primera vez en 1959 por Weidenfeld & Nicolson.