Do ósmego roku życia Leskow przebywał głównie w dworze w Gorochowie, który stanowił własność męża jego ciotki – Michaiła Strachowa. Zarządcą majątku Strachowa był dziadek przyszłego pisarza Piotr Ałfierjew. Razem z jego dziećmi Nikołaj Leskow uczył się u prywatnego guwernera języków francuskiego i niemieckiego. W 1839 wrócił do rodzinnego domu w Paninie i pozostawał tam przez dwa lata, do momentu rozpoczęcia nauki w gimnazjum w Orle. Nie uzyskał dyplomu końcowego tejże szkoły – przez pięć lat zdołał ukończyć trzy z ośmiu klas, po czym przerwał naukę. Przyczyną szkolnego niepowodzenia był fakt, że pozostawiony w mieście bez kontroli ze strony rodziców Leskow spędzał czas na czytaniu literatury pięknej, nie zaś na nauce. W Orle Leskow zetknął się również z ukraińskim etnografem Opanasem Markowiczem i jego żoną Marią, w przyszłości cenioną literatką rosyjską i ukraińską.
Siemion Dmitrijewicz Leskow zdołał uzyskać dla syna stanowisko kancelisty II kategorii w orłowskiej izbie karnej, następnie przyszły pisarz pełnił obowiązki pomocnika referenta. W 1849 r. jego wuj, Siergiej Ałfierjew, profesor medycyny na Uniwersytecie Kijowskim, zdobył dla niego pracę w komisji poborowej w Kijowie.