Родился в крестьянской семье. Отец — Леонов Сергей Михайлович (род. 1903), мать — Трифонова Наталья Владимировна (род. 1906). В 1938 году семья переехала в город Электросталь. В 1947 окончил среднюю школу с золотой медалью, после чего поступил в Институт международных отношений.
По окончании института он был направлен в непрестижное место по причине конфликта с министром иностранных дел А. Я. Вышинским — в издательство литературы на иностранных языках. В мае 1953 его направили на стажировку в Мексику, куда он отправился на торговом судне «Андреа Гритти» из порта в Генуе. На нём он познакомился с Раулем Кастро. После прибытия Леонов стал учиться в университете Мехико (Национальный автономный университет Мексики) на факультете филологии и философии, став чиновником в посольстве.
Летом 1956 года Николай Сергеевич познакомился с Че Геварой. Однако через несколько дней эту группу кубинских революционеров арестовали, а при обыске у Гевары нашли карточку Леонова. Это стало причиной для возврата Николая Сергеевича на Родину в то же издательство.
В 1958 году был принят в 101-ю школу КГБ для подготовки в качестве разведчика. В 1959 — в составе делегации, возглавляемой заместителем Председателя Совета министров СССР А. И. Микояном поехал в Мексику, а затем — на Кубу, где встретился со своим другом Фиделем Кастро. С 1960 года Леонов в разведке в Латинской Америке против спецслужб США. Ему пришлось принять активное участие во многих событиях, связанных с борьбой против американского влияния в странах Латинской Америки. Также он бывал в краткосрочных командировках в Афганистане и других странах.
Сопровождал и переводил Ф. Кастро в его поездке по СССР в 1963 году.
В 1971 году Леонов стал заместителем начальника информационно-аналитического управления внешней разведки. В сентябре 1983 — заместителем начальника разведки.
С 30 января по 27 августа 1991 года — начальник аналитического управления КГБ СССР.
Прогнозы аналитиков, которыми Леонов руководил 12 лет, ни разу не оказались ошибочными.
В 1991 году в связи с распадом СССР Леонов ушёл в отставку. Совместно с друзьями из КГБ он организовал АО «Российская национальная служба экономической безопасности». С 1994 преподаёт в МГИМО. С 1996 — сотрудничает с журналом Русский дом, в котором до сих пор пишет аналитические статьи, так же принимал участие в телепередаче «Русский дом» вплоть до её закрытия. Депутат Государственной Думы РФ IV созыва (2003—2007) от блока «Родина».
В 2005 подписал письмо 5000.
Женат на Кондыревой Евгении Николаевне (род. 1946), двое детей. Н. С. Леонов — православный христианин, его духовник — архимандрит Тихон (Шевкунов).