В 1769 году Нелединский со своими двоюродными братьями Куракиными поехал учиться в университет г. Страсбурга (Франция), но через год, по жалобам приставленного к нему гувернера, был возвращен в Петербург.
В 1770 году Нелединский, который еще с шести лет числился на службе в армии, отправился на театр военных действий во Вторую армию, которой командовал Петр Иванович Панин, родной дядя его матери. Нелединский был назначен ординарцем к Панину, отправлен с донесением в Петербург и получил чин поручика. Затем, после отставки Панина, он переведен был в егерский корпус, участвовал в завоевании Крыма и произведен в капитаны, в кампании 1774 года служил в передовом корпусе генерала М. Ф. Каменского, был в сражении под Шумлой, вынудившем турок просить мира. В свите фельдмаршала Н. В. Репнина, своего родного дяди, Нелединский вернулся в Петербург, где получил чин премьер-майора.
Вместе с Репниным, назначенным послом в Турцию, Нелединский в качестве кавалера посольства находился в 1775—1776 годах в Константинополе. В 1776-—1785 годах он продолжает военную службу, сначала в Псковском пехотном полку, затем в Киевском. На эти годы приходится его переписка с петербургскими дамами и сочинение большинства его любовных стихов и песен, вдохновленных глубоким чувством к женщине, имя которой Нелединский тщательно скрывал даже от своих друзей. В это же время он занят был переводом трагедии Вольтера «Заира».
В 1785 году Нелединский по его «прошению» получил отставку в чине полковника. Он поселился в Москве и в 1786 году женился на княжне Екатерине Николаевне Хованской, только что выпущенной из Смольного института благородных девиц.
В Москве Нелединский сближается с писателями Херасковым, Карамзиным, Дмитриевым. В «Московском журнале» впервые печатаются его песни, до того расходившиеся только в списках. Имя поэта, известное ранее только узкому кругу светских знакомых, становится популярным в литературных кругах, хотя стихи свои он печатает без подписи.
После смерти Екатерины II Павел, в числе других знакомцев своей молодости, призвал на службу Нелединского и сделал его своим статс-секретарем для принятия прошений, то есть докладчиком. Нелединский пробыл в этой должности два года, до своего неожиданного увольнения в 1798 году по интриге Кутайсова. В 1800 году Нелединский, в числе других прощенных, возвратился на службу и был назначен сенатором в Москве.
После смерти Павла Нелединский — один из приближенных вдовствующей императрицы Марии Федоровны, и каждое лето навещает ее в Павловске. В 1804—1813 годах он живет в Москве, а с 1813-го по 1826 год — в Петербурге. В 1826 году Нелединский вышел в отставку, поселился в Калуге и там умер.
Литератором в собственном смысле слова Нелединский никогда не был, в молодости он был салонным дилетантом-стихотворцем, в зрелом возрасте он писал уже только стихи на случай — для «домашнего употребления». Но у этого дилетанта оказался несомненный поэтический дар, верно оцененный Карамзиным и Дмитриевым. Никогда не помышлявший об издании своих стихов отдельным сборником, Нелединский только после публикации в «Московском журнале» (1792) и «Карманном песеннике» (1796) Дмитриева занял скромное, но прочное место среди русских поэтов 1790—1820-х годов. Критика не часто его вспоминала. Но читатели и поэты не забывали.
В 1825 году, еще при жизни Нелединского, в «Северных цветах» Дельвиг напечатал свой «Романс», в котором высказал отношение поэтов пушкинского круга к «певцу Темиры» словами человека «Екатеринина века», обращенными к молодым:
