Николай Столетов завършва университета през годината, когато започва Кримската война и като доброволец се отправил в Крим. Започнал да служи като артилерист в 10-та артилерийска бригада, в състава на която участва в битката за Инкерман и в отбраната на Севастопол.
По време кампания в Севастопол с Николай Столетов се случил любопитен инцидент. В стрелковото укрепление на единадесетата артилерийска бригада той срещнал офицер, командващ това подразделение.
„Разговорихме се – спомня си по-късно Столетов, – изпитах огромно удоволствие от това запознанство; офицерът беше приятелски настроен и пред самовара, който се беше появил в палатката, имахме възможност да си побъбрим. „
На следващата сутрин артилеристите, изпитващи симпатия един към друг, не им се искало да се разделят, но служебният дълг го изисквал. За спомен новият познат на Столетов му подарил, написан за няколко минути, шеговит разказ „За нощното пробуждане“.
„Много се зарадвах да получа този малък знак на внимание, вместо обикновения лист хартия – спомня си по-късно Столетов, – на който съвсем официално бях написал своето звание: старши фойерверкер, собствено име, бащино име и фамилия. Бях радостен, че този разказ ми беше оставен за спомен, но действителният подпис, поставен под него, ме трогна изключително много години по-късно. Под разказа стоеше: „Лев Николаевич Толстой, поручик от артилерията“.
Толстой във военната си униформа през 1856 година
Николай дълго време пазил автографа на Толстой, но през 1870 г. в Красноводск, по време на нападението на туркмените, това скъпо късче изчезнало… Тези двама артилерийски офицери запазили топли чувства един към друг до края на живота си и когато се срещали, неизменно си припомняли годините на страдание в Севастопол.
През 1910 г. Николай Григориевич изпраща великия писател и негов приятел в последния му път.