Действительный тайный советник (с 17.04.1894), камергер (с 1874). Из древнего дворянского рода, восходящего к XIV в. Сын директора училищ Бессарабской губернии, статского советника Ивана Александровича Нелидова (1799—1853) от брака с Александрой Петровной Яновской (ум. 1884). Родился в селе Дубровки Поречского уезда Смоленской губернии. Среднее образование получил в Кишинёвской гимназии, окончив её с золотой медалью, высшее — в Петербургском университете на факультетах: юридическом и восточных языков; курс в университете также окончил с золотой медалью. 13.12.1855 в чине коллежского секретаря начал службу в Азиатском департаменте МИД. С 1856 и.д. младшего секретаря, с 1858 - младший секретарь российской миссии в Греции. В 1861—1864 младший, а в 1864—1869 старший секретарь миссии в Баварии. В 1862 пожалован в камер-юнкеры Высочайшего Двора, в 1864 получил чин надворного советника. В 1869—1874 старший секретарь российского посольства в Вене. С 1871 статский советник. В 1874—1877 советник российского посольства в Константинополе; тайно провел переговоры в Бухаресте с румынским премьер-министром И. Братиану о пропуске Румынией русских войск через свою территорию в случае войны с Турцией. С 16.12.1875 в чине действительного статского советника. Во время русско-турецкой войны 1877—1878 состоял директором дипломатической канцелярии при главнокомандующем действующей армией вел. князе Николае Николаевиче (старшем), принимал участие во всех походах и передвижениях Главной квартиры, а также в переговорах с турецкими уполномоченными в Казанлыке и Адрианополе; составил предварительные условия мира с Турцией. В 1878 вместе с генерал-адъютантом Н.П. Игнатьевым подписал, в качестве уполномоченного, Сан-Стефанский мирный договор с Турцией. Участвовал в работе Берлинского конгресса 1878.
В 1879—1882 Нелидов занимал должность посланника в Саксонии и герцогстве Саксен-Альтенбург, затем снова получил назначение в Турцию — сначала в качестве управляющего посольством, а с 15.07.1883 — в качестве посла. 15.05.1883 произведён в тайные советники. Сторонник захвата черноморских проливов, в декабре 1882 он направил Александру III записку «О занятии проливов», в которой утверждал: «Можно легко предвидеть, что в дальнейшем распадение Турецкой империи будет совершаться тем же путем, как совершалось распадение империи Византийской, доколе сама столица не будет завоевана... Эта роль завоевательницы столицы, как кажется, предназначена судьбою и историей России, которой все интересы политические, торговые и военные настоятельно требуют занятия проливов... Вопрос тут... в утверждении русской власти на пути наших южных морских сообщений с открытыми морями и океаном. Кроме того, утверждение на Босфоре окончательно закрепляет за нами все наши закавказские владения, соединяет в одном пункте всю нашу оборонительную линию берегов Черного моря и дает нам решитеьлное влияние на судьбы как Балканского, так и Малоазиатского полуостровов. Наконец, оно усиливает оборонительную силу нашу на западной границе, давая нам возможность располагать для ее защиты всеми боевыми средствами, которые были доселе мобилизованы на черноморских берегах.... Царьград должен быть и оставаться городом независимым, принадлежащим только самому себе. Но он должен состоять под нашим покровительством, охраняться нашими войсками, содержать их и, может быть, платить нам дань за оказываемую ему защиту. Присоединение его к России расширило бы чрезмерно наши границы, восстановило бы против нас местное население и ослабило бы нас самих. Тогда как, оставленные нами политически и административно свободными, жители Византии и ее небольшой территории (с некоторыми пунктами на Дарданеллах) видели бы в русском протекторате залог и источник своей безопасности и своего благосостояния». 15.05.1883 получил чин тайного советника. Нелидов был противником прогерманской политики, проводившейся министром иностранных дел Н.К. Гирсом и его ближайшими сотрудниками, и несколько раз возбуждал вопрос о заключении союза с Францией. Это предложение не было поддержано Гирсом, но вскоре франко-русский союз стал совершившимся фактом. Опасаясь морского нападения Великобритании на Черноморское побережье России, в 1885–1886 Нелидов вёл секретные переговоры с султаном Абдул-Хамидом II о заключении русско-турецкого союза по вопросу о Черноморских проливах и поддержании статус-кво на Балканах. В области европейской политики был противником прогерманского курса Н.К. Гирса, несколько раз возбуждал вопрос о заключении союза с Францией. В период Болгарского кризиса 1885–1887 призывал российское правительство отказаться от планов возвращения Восточной Румелии Османской империи и выступить с инициативой признания объединения Болгарии, участвовал в Константинопольской конференции послов по Болгарскому вопросу (1885–1886), выступал против планов оккупации Болгарии российскими войсками с целью смещения с престола князя Александра I Баттенбергского. В 1894 предпринял первые шаги по восстановлению дипломатических отношений с Болгарией.
Во время Ближневосточного кризиса 1890-х, спровоцированного репрессивной политикой турецкого правительства в отношении армянского населения, пытался урегулировать конфликт, совместно с послами Франции и Великобритании в Константинополе участвовал в выработке проекта реформ для шести вилайетов Западной Армении. Осенью 1896, в условиях обострения кризиса и возможного распада Османской империи, инициировал новое обсуждение разработанного ранее проекта захвата Босфора силами российской армии и флота. План был одобрен 17.11.1896 на совещании у Николая II. Нелидов уехал в Константинополь, чтобы оттуда дать в своё время шифрованную депешу командующему Черноморской эскадрой. Однако Николай II отказался от осуществления плана из-за противодействия министра финансов С.Ю. Витте и отказа Франции поддержать действия России. Великий визирь Кямаль-паша говорил, что Нелидову в Константинополе удалось «склонить султана вполне в сторону русской политики. Султан доверял послу больше, чем своему турецкому правительству». В итоге Порта настояла на его отзыве.
В 1897 был переведен на пост посла в Рим. В 1898 участвовал в межгосударственной конференции в Риме по вопросу борьбы с анархизмом и терроризмом. Его донесения, предупреждающие о том, что приезд Николая II в Италию может вызвать враждебные демонстрации, сорвали визит российского императора. Это возбудило недовольство короля Виктора Эммануила III, потребовавшего отозвания Нелидова. 1.11.1903 был переведён в Париж, где оставался до самой смерти. Время пребывания Нелидова в Риме и Париже совпало с русско-японской войной 1904—1905, и Нелидов оказал ряд важных услуг России: его влияние сказалось на благоприятном для России исходе Гулльского инцидента; он способствовал усилению русского флота двумя крупными единицами. Активно содействовал укреплению Русско-французского союза, привлечению французских инвестиций и займов для нужд российской экономики. Председатель 2-й Гаагской конференции мира (1907). Видный российский дипломат, Нелидов был удостоен ряда российских орденов, включая Св. Владимира 3-й степ. (1873), Св. Станислава 1-й степ. (1877), Св. Анны 1-й степ. с мечами (1877), Св. Владимира 2-й степ. (1881), Белого Орла (13.04.1886), Св. Александра Невского (1.04.1890, алмазные знаки к ордену - 13.04.1897), Св. Владимира 1-й степ. (6.04.1903) и Св. Андрея Первозванного (13.12.1905, алмазные знаки к ордену - 1908) включительно, а также иностранных орденов, включая Короны кавалерского креста (Бавария, 1864), Спасителя офицерского креста (Греция, 1865), Св. Людвига кавалерского креста (Гессен-Дармштадт, 1866), Независимости Чёрной Горы 2-й степ. (Черногория, 1872), Франца-Иосифа 2-й степ. со звездой (Австро-Венгрия, 1872), Меджидие 2-й степ. со звездой (Османская империя, 1874), Саксен-Эрнестинского Дома большого креста (Саксен-Кобург-Гота, 1881), Кн. Даниила I за независимость Чёрной Горы 1-й степ. (Черногория, 1881), Альберта 1-й степ. (Саксония, 1882), Османие 1-й степ. (Османская империя, 1882, бриллиантовые знаки к ордену - 31.05.1891), Вендской Короны 1-й степ. (Мекленбург-Шверин, 29.10.1890), Спасителя 1-й степ. (Греция, 27.06.1891), Имтияза золотую и серебряную медали (Османская империя, 16.06.1893), Льва и Солнца 1-й степ. с бриллиантами (Персия, 1894), Белого Орла 1-й степ. (Сербия, 12.03.1896), Св. Александра 1-й степ. (Болгария, 30.12.1896), Св. Маврикия и Лазаря большого креста (Италия, 5.10.1902), Почётного легиона большого креста (Франция, 15.12.1905). Имел также знаки отличия беспорочной службы за 40 (22.08.1899) и 50 лет на Владимирской ленте (22.08.1909), османские золотую и серебряную медали Имтиаза (1893). Почётный член Имп. Германского археологического института (25.04.1903). Скончался в Париже от рака кишечника на 76-м году жизни, похоронен в России, на Никольском кладбище Александро-Невской лавры в С.-Петербурге.
Был женат (с 30.05.1862) на княжне Ольге Дмитриевне Хилковой (1839-1918), дочери действительного статского советника князя Д.А. Хилкова. Она увлекалась литературой и выступала в печати с переводами. По словам дипломата Ю.С. Карцова, была женщина очень неглупая и приятная в разговоре, а И.С. Тургенев отзывался о ней как о прелестной и весьма образованной девушке. В обществе О.Д. Нелидова была известна своими легкомысленными любовными связями, из-за которых в 1894 Австро-Венгрия отказалась принять у себя Нелидова послом. Будущий министр иностранных дел В.Н. Ламздорф писал в дневнике, что было бы «совершенно невозможно, чтобы пресловутая Ольга Дмитриевна, которую недолюбливала императрица Мария Фёдоровна, оказалась принятой при австрийском дворе и допущена в венское общество». За заслуги мужа в коронацию имп. Николая II в 1896 была пожалована в кавалерственные дамы ордена Св. Екатерины (меньшого креста). После его смерти осталась жить во Франции, состояла председательницей Комитета русских дам в Париже. Супруги имели детей: Д.А. Нелидова, Ивана Александровича (1865—1904), лейтенанта, участника перехода 2-й Тихоокеанской эскадры из С.-Петербурга во Владивосток на броненосце «Ослябя» и скончавшегося от теплового удара за полгода до гибели эскадры в Цусимском сражении; Георгия Александровича (1874-1918), статского советника, управляющего Отделом печати МИД (1914-1916); Александра Александровича (1885-?); Владимира Александровича (1887-1978).
