После того, как «Олимпия Пресс» опубликовала в 1955 году «Лолиту» на английском языке, в декабре 1956 года книга была запрещена во Франции. Издатель, Морис Жиродиа, обратился к Набокову с просьбой помочь в борьбе с запретом, на что автор ответил: «Моя моральная защита книги — это сама книга». Он также написал эссе «О книге, озаглавленной «Лолита»» — многословное оправдание, опубликованное позже в американском издании романа. В нем автор утверждал, что читатели, которые сочли произведение эротическим, неверно поняли его замысел. «То, что мой роман содержит немало ссылок на физиологические позывы извращенного человека — отрицать не могу. Но в конце концов мы не дети, не безграмотные малолетние преступники и не питомцы английского закрытого среднеучебного заведения, которые после ночи гомосексуальных утех должны мириться с парадоксальным обычаем разбирать древних поэтов в почищенных» изданиях», — заявляет Набоков.
«Олимпия Пресс» выиграла дело в 1957 году в Парижском административном суде, и роман вернулся на прилавки в январе 1958 года. Когда в мае 1958 года пала Четвертая республика и к власти пришел генерал Шарль де Голль, министр внутренних дел обратился в Государственный совет, Верховный суд Франции. К декабрю того же года книгу вновь запретили — правительству удалось добиться восстановления прежнего приговора. Апелляция была невозможна, но публикация перевода романа на французский престижным издательством «Галлимар» в апреле 1959 года дала «Олимпии Пресс» основания для подачи жалобы. Издатель предъявил правительству иск: по мнению издательства, юридический принцип равенства граждан был нарушен, ибо издание «Лолиты» «Олимпии Пресс» было запрещено, а «Галлимар» — нет. В сентябре 1959 года английский перевод вернулся на французский рынок.
Британское таможенное ведомство запретило книгу в 1955 году. В том же году Грэхам Грин назвал «Лолиту» на страницах «Санди Тайме» в числе трех лучших, по его мнению, книг года. В ответ на статью Грина, Джон Гордон заметил в «Санди Экпресс»: «Без сомнения — это самая грязная книга из тех, что мне приходилось читать. Абсолютно необузданная порнография». Несколько британских издателей страстно желали поторговаться за права на издание романа, но они ждали принятия в 1959 году «Списка непристойных изданий». Последний должен был позволить принимать во внимание, в качестве аргумента, литературные достоинства книги. Издатели ждали начала судебного преследования, ибо литературные обозреватели уже поговаривали о войне против романа; некоторые заявляли, что книгу следует запретить в Англии, если будет доказано, что «хотя бы одна маленькая девочка может быть совращена вследствие этой публикации». Консерваторы в парламенте убедили Найджела Николсона, члена парламента и издателя, не публиковать книгу, заявив, что это повредит имиджу партии. Он лишился возможности быть вторично избранным, отчасти из-за «Лолиты».
Таможенное ведомство США, напротив, установило в феврале 1957 года, что книга не является предосудительной и может ввозиться в страну.
Таким образом, книгу нельзя было легально вывезти из Франции, но те, кому удалось провезти ее контрабандой, могли совершенно законно ввозить ее в США. Несмотря на толерантность таможни, американские издатели отказывались публиковать «Лолиту», пока в 1958 году не решило рискнуть издательство «Дж. П. Путнамз Санз». Год спустя были сняты запреты во Франции и Англии и книга открыто издавалась в обеих странах. В США, однако, Публичная библиотека Цинциннати убрала книгу с полок после заявления директора: «тему извращения я считаю неприличной».
Роман был, кроме того, запрещен в 1959 году в Аргентине, где правительственные цензоры посчитали, что в книге изображено моральное разложение. В 1960 году в Новой Зеландии запретили ввоз романа, согласно Таможенному акту 1913 года, запрещающему импорт книг, считающихся «непристойными» в соответствии с «Законом о непристойных изданиях» от 1910 года. В борьбе с запретом новозеландский Совет по гражданским свободам ввез шесть экземпляров книги и успешно опротестовал запрет в Верховном суде. Судья Хатчин, вынося приговор, заметил, что порнография не являлась целью написания книги, адресованной образованному читателю. Основывая свое решение на рекомендации совещательного комитета министерства (согласно которой в отдельных случаях можно разрешать провоз книги), судья заметил, что таможня Новой Зеландии пропускала некоторые книги, адресованные определенным персонам или предназначенные для продажи узкому кругу читателей. Запрет на «Лолиту» в ЮАР, наложенный в 1974 году из-за «темы извращения» в романе, был снят в 1982 году, а Управление публикаций ЮАР дало разрешение на издание книги в мягкой обложке.