Только спустя год, в августе 1961 года, Н. С. Трубин получил повышение — он возглавил прокуратуру Новотитаровского района. С этого времени и начинается его неспешное, но уверенное восхождение на прокурорский Олимп. Не прошло и двух лет, как он был выдвинут на работу в аппарат краевой прокуратуры. В марте 1963 года он становится прокурором следственного отдела, а уже в августе — старшим помощником прокурора края по кадрам. В сентябре 1964 года ему присвоили очередной классный чин — советника юстиции.
Николай Семенович с головой ушел в новую для него работу. Если раньше он сам отвечал за то, как осуществлялся надзор за исполнением законов, то теперь ему пришлось больше приглядываться к людям, вникать в их заботы, ведь в прокуратуре края тогда насчитывалось почти 260 человек. Для пополнения ее квалифицированными юристами, способными по своим моральным и волевым качествам к трудной прокурорско-следственной деятельности, он установил тесную связь с Краснодарским факультетом Всесоюзного юридического заочного института. Студенты старших курсов (4-го и 5-го), соответствующие, по его мнению, этим требованиям, брались им на заметку. Он беседовал с каждым из них, а лучших приобщал к работе в прокуратуре на общественных началах, создавая тем самым резерв для замещения вакантных должностей. Только за 1965 год из этого резерва были приняты на работу 18 человек. Такая практика вполне себя оправдывала. Постепенно увеличивалась прослойка работников прокуратуры с высшим и незаконченным высшим юридическим образованием (их стало более 90 процентов). Однако проблемы с кадрами оставались. Не все выдерживали напряженный ритм работы в органах прокуратуры, поэтому почти 30 человек ежегодно увольнялись и не все по «собственному желанию».
И все же работа с кадрами не вполне удовлетворяла Н. С. Трубина. Его больше привлекала та сторона деятельности прокуратуры, которая была связана с расследованием преступлений. И когда представилась возможность, он обратился с просьбой к прокурору края Корсакову о переводе его на следствие. В январе 1966 года Николай Семенович возглавил следственный отдел прокуратуры края. В этой должности он задержался дольше всего — шесть лет. Весной 1967 года Н. С. Трубин как молодой еще руководитель стажировался в следственном управлении Прокуратуры РСФСР, причем знакомился не только с аппаратной работой, но и побывал на местах — в Свердловске, где некогда прошла его юность, и в прокуратуре Московской области. Все это ему помогло в дальнейшем. Отдел, возглавляемый Трубиным, был на хорошем счету, а инициативного начальника приметили в союзной прокуратуре.
В январе 1972 года начальник отдела по надзору за следствием и дознанием в органах МВД следственного управления Прокуратуры Союза ССР Г. П. Каракозов обратился к заместителю Генерального прокурора СССР А. С. Панкратову с рапортом о назначении Н. С. Трубина прокурором отдела. С этим был согласен и заместитель Генерального прокурора СССР — начальник следственного управления Н. В. Жогин. Взяли Трубина с явным намерением на выдвижение, так как уже через четыре месяца он стал заместителем начальника отдела. С января 1974 года Н. С. Трубин одновременно выполнял и обязанности помощника Генерального прокурора СССР. Ему присвоили чин государственного советника юстиции 3-го класса. Прошел еще год, и Николай Семенович получил уже солидную должность — заместителя начальника следственного управления Прокуратуры Союза ССР.
В апреле 1976 года Н. С. Трубин, как один из опытнейших криминалистов страны, был направлен в заграничную командировку — на Кубу. Там он выполнял обязанности советника Генерального прокурора Республики Куба, Сантьяго Куба Фернандеса. На острове Свободы Николай Семенович прожил чуть более года, завоевав любовь и признательность не только работников прокуратуры, но и представителей партийных и государственных органов республики. Он вел там обширную педагогическую деятельность — читал лекции по криминалистике, уголовному, уголовно-процессуальному, исправительно-трудовому праву (впоследствии они были опубликованы в кубинских методических сборниках), участвовал в подготовке проектов законов о прокурорском надзоре в Республике Куба и об уголовном судопроизводстве, консультировал Генерального прокурора. В письме, адресованном Н. С. Трубину, представители общественных организаций Генеральной прокуратуры писали:
«Уважаемый товарищ, Николай Трубин.
Разрешите нам этими скромными строками от имени партийной, комсомольской (СМК) и массовых организаций Генеральной прокуратуры Республики, а также от имени всех ее сотрудников выразить глубокое уважение, которое мы питаем к Вам лично. Это чувство по праву заслужено Вами ежедневной работой и человеческой теплотой, которая проявлялась постоянно.
Было бы некорректно попрощаться с Вами, не сказав до этого о высокой оценке Вашей работы в качестве советника Генерального прокурора и о ее полезности.