Нелаев Алексей Павлович был призван на военную службу в январе 1937 года Великоустюгским райвоенкоматом. До августа 1937 года был в учебном отряде города Кронштадт,где получил специальность электрика. Служил на сторожевом корабле "Снег",на эсминце "Калинин", а с марта 1941 года по февраль 1946 года на эсминце "Строгий" Краснознаменного Балтийского Флота в должности старшины электромоторной группы. Когда началась Великая Отечственная война, корабль был выведен на огневую позицию в Новосаратовскую колонию. Отсюда в 1941-1943 годах эсминец"Строгий" огнем своих орудий громил фашистов защищая город Ленинград.По Неве ходили до Лесопарка, оттуда вели огонь по немецким позициям на Синявских болотах. Бывало что на позиции стояли по 7-8 суток;стрельба шла круглосуточно, краска на орудиях сгорала от перекала. Только с 21 июля по декабрь 1941 года эсминец "Строгий"выпустил по танковым колоннам,по автоколоннам с вооружением,продовольствием и живой силой врага 4600 снарядов из 130-миллиметровых орудий(данные командира корабля "Строгий" Новака Владимира Романовича).Корабли Балтийского Флота в том числе и эсминец "Строгий", внесли огромный вклад в дело прорыва блокады Ленинграда.В 1944 году после прорыва блокады Ленинграда корабль ушел в город Кронштадт, откуда и вел огонь по врагу.

За участие в боях старшина I статьи Нелаев Алексей Павлович был награжден орденом Красной Звезды, медалью "За оборону Лененграда", медалью " За Победу над Германией".

  Боевой орден им был получен за то, что, когда во время боя (1943году) от сильного сотрясения при одновременной стрельбе залпом из двух носовых орудий была нарушена подача энергии в центральный артиллерийский пост, он ладонью прижал контактор, обеспечив бесперебойную подачу энергии на время ведения огня. При этом он был контужен.

После войны он был награжден орденом Великой Отечественной войны II степени и многими юбилейными медалями.

Демобилизован в феврале 1946 года.9 лет жизни отдано службе на флоте.Умер 22 марта 2010 года в городе Великий Устюг.