Родился в семье Якова Наумовича и Марии Натановны Эйдельман. Окончил исторический факультет МГУ в 1952 году.
После окончания университета Натан Эйдельман шесть лет работал преподавателем истории в вечерней школе в подмосковном городе Ликино-Дулёво, а с 1954 года — в Москве. Затем в должности научного сотрудника работал в Московском областном краеведческом музее в городе Истре.
После 1956 года имел косвенное отношение к университетскому кружку свободомыслящих историков, в котором состояли некоторые его однокурсники, занимавшиеся критикой сталинизма с марксистских позиций. Арест членов этого кружка вынудил Эйдельмана прекратить преподавание истории в школе, хотя он сам, не будучи членом этого кружка, не был репрессирован, но был вынужден выйти из КПСС.
В 1965 году он защитил кандидатскую диссертацию на тему «Тайные корреспонденты „Полярной звезды“».
Основной областью научных интересов Эйдельмана была история русской культуры и общественное движение России в XVIII—XIX веках. Главным направлением его исследований было движение декабристов. Его работам был свойственен особо внимательный подход к нравственной трактовке рассматриваемых событий. Мысли героев его книг, посвятивших себя борьбе за свободу в России, оказывались, благодаря Эйдельману, неожиданно актуальными в условиях советской действительности, что, наряду с хорошим литературным языком его книг, способствовало росту популярности его книг и публицистики среди критически настроенной части советской интеллигенции. С 1971 года Н. Я. Эйдельман был членом Союза писателей СССР.
Немалую часть своих работ он посвятил проблемам русско-кавказских культурных связей, роли Кавказа и его народов в жизни и культуре России. В то же время по мнению ряда источников еврейская тема практически никогда не привлекала внимание Эйдельмана.
Однако в острой переписке, впоследствии опубликованной в журнале «Даугава», он, полемизируя с писателем Виктором Астафьевым, затрагивал тему межнациональных отношений в том числе и русско-еврейских, но по мнению некоторых, например, авторов Электронной еврейской энциклопедии, при этом в своих аргументах в этой переписке «придерживается определенных антиеврейских предрассудков».
В целом, определенно можно считать Натана Эйдельмана одним из ярчайших представителей гуманитарного крыла интеллигенции, внесший немалый вклад в развитие русской культуры второй половины XX века.