Тенниел на протяжении 50 лет был одним из самых востребованных лондонских карикатуристов. Его работы каждую неделю выходили в сатирическом журнале «Панч». Помимо Тенниела здесь печатались Милн и Джером. Из-за частичной потери зрения Джон не мог заниматься живописью, а потому сосредоточился на графике.
К работе над сказкой «Алиса в стране чудес» Кэрролл приступил в 1862-м. Он рассчитывал закончить её за несколько месяцев, однако дело затянулось на 2 года. Автор переписывал рукопись несколько раз. Первоначально он задумал работать над иллюстрациями самостоятельно, но затем решил обратиться к профессионалу. Выбор пал на Тенниела; писатель покупал каждый номер журнала «Панч» и ценил мастерство иллюстратора.
Кэрроллу нужен был не просто художник, а человек, которому привычны аллюзии и метафоры. Но избежать творческих разногласий всё же не удалось. О совместной работе писатель отзывался: «Мистер Тенниэл, единственный из иллюстрировавших мои книги художников, наотрез отказался рисовать с натуры, сказав, что она ему так же не нужна, как мне для решения математической задачи — таблица умножения! Я склонен думать, что он ошибался и что из-за этого некоторые рисунки в «Алисе» непропорциональны — голова слишком велика, а ноги — слишком малы». Всего Тенниел создал 42 иллюстрации, при этом каждую из них он обсуждал с автором. В работе он использовал и эскизы писателя.
Некоторые персонажи Тенниела являются карикатурами на политиков. Так, Лев и Единорог, которых Алиса встречает в Зазеркалье, связаны с фигурами видных деятелей Англии 19-го века: Уильямом Гладстоном и Бенджамином Дизраэли. Шляпник — карикатура на торговца мебелью из Оксфорда, который отличался эксцентричным поведением. Прообразом Герцогини стала правительница независимого Тирольского царства Маульташ (1318−1369), считавшаяся самой уродливой женщиной в Европе. Маульташ переводится как «пельмень», что, очевидно, является намёком на внешность девушки.
Кэрролл требовал от Тенниела полностью следовать авторской задумке, однако художник всё же допустил некоторые вольности. Так, в книге у Алисы тёмные короткие волосы, она носит чёлку. Иллюстратор видел персонажа иначе. Его Алиса — девочка с длинными светлыми волосами.
«Алиса в стране чудес» пользовалась огромным успехом. С 1869-го по 1890-й книга издавалась больше 20 раз. Кэрролл привлёк художника и к работе над «Алисой в Зазеркалье». По рекомендации Тенниела он убрал из сказки главу «Шмель в парике». Она была издана в 1871 году.