Сразу же после приезда в Бухарест Паренсов направился к барону Стюарту и представил ему рекомендательное письмо начальника Полевого штаба. Обсудив с Паренсовым несколько вариантов его представления окружающим, барон остановился на следующем: полковник — вологодский помещик для русских, а Пауль Паульсон — кузен барона — для остальных. Инкогнито Паренсова было тут же раскрыто румынскими властями. Барон очень скептически отнесся к идее посещения Рущука и, по сути, повторил рекомендации Хитрово, на кого можно рассчитывать в разведывательной работе. Высказался Стюарт и по поводу выделенной на нужды разведки суммы — 3000 рублей. По его мнению, «это положительно мало и что не в том дело, чтобы истратить деньги, а в том, чтобы иметь их в данную минуту под рукой».

Помощь дипломатического агента России в Бухаресте барона Стюарта и 2-го секретаря консульства Золотарева оказалась основополагающей в деле создания агентурной сети Паренсовым.

Вскоре при посредничестве Стюарта Паренсов «познакомился с двумя интересными субъектами: первый был скопческий староста Матюшев, а второй — богатый болгарин — банкир Евлогий Георгиев». Проживавшие в Румынии скопцы, хотя и считались румынскими подданными, но находились в то же время под протекторатом русского консульства, которое почиталось ими чуть ли не больше румынского правительства. Объяснялось это тем, что ни один скопец не мог въехать в Россию без особого в каждом случае отдельного разрешения российского консула. Скопцы в Турции преследовались полицией и изгонялись из пределов Оттоманской империи. Таким образом, их можно было привлекать к разведывательной деятельности в пределах Румынии, и в первую очередь на нижнем Дунае — о движении турецких судов, о запасах продовольствия, заготавливаемого турецкими агентами в Галаце и Браилове.

Евлогий Георгиев, холостой миллионер, ревностный патриот, безвозмездно финансировал болгарское освободительное движение. Источником его богатства, кроме банковских операций, являлась значительная хлебная торговля. Склады зерна имелись во многих придунайских городах: Ольтинице, Галаце, Журжеве и далее вплоть до Калафата, а также имелись его представители в Шумле, Рущуке, Систове, Габрове и др. населенных пунктах. Георгиев охотно вызвался содействовать сбору сведений о турках. Евлогий Георгиев, по словам Паренсова, «взял на себя роль 1-го агента, а для поручений особой смышлености и в то же время требующих смелых и рискованных путешествий, выписал из Вены своего коммерческого агента, Начовича, говорящего по-французски».

Происходивший из богатой болгарской семьи, занимавшейся торговлей, Георгий Начович имел большие связи и знакомства по обе стороны Дуная, «был неисчерпаем в изобретении способов и уловок добывать сведения», сделался ближайшим помощником Паренсова, «правой его рукой и продолжал свою дея-тельную работу до перехода нашей армии через Дунай». Деятельность Начовича была бескорыстна и безвозмездна — за все время сотрудничества с разведкой он ни разу не взял денег за свои труды.

Вскоре с помощью Начовича было подобрано несколько агентов, которые были отправлены за Дунай на турецкую территорию: один был послан в Рущук, другой — в Шумлу и третий — в Турн-Магурели и Никополь. Инструкции агентам давались устные, «причем, конечно, приходилось читать целые лекции разных военных наук и прорепетировать уроки». Все это было далеко не просто, так как приходилось обращаться к услугам переводчика, если таковым не выступал Начович. Давать письменные инструкции, как вскоре понял Паренсов, было весьма опасно, во-первых, для самого направляемого, во-вторых, перед противником раскрывались детали проявляемого к нему интереса.

Вместе с тем переправа через Дунай, перемещение по заранее обговоренному маршруту и возвращение назад, вновь через широкую реку, далеко не всегда были под силу одному разведчику — «агенту-ходоку». Поэтому вся задача добывания разведывательных сведений нередко дробилась Паренсовым с его помощниками на несколько частных, не менее ответственных, сложных и опасных задач, выполняемых различными людьми.

«Для ускорения дела» приходилось иногда посылать Начовича со словесными инструкциями к другому агенту в одном из прибрежных мест Дуная (на румынском берегу), а последний, в свою очередь перебравшись через Дунай, передавал поручение третьему агенту. По сути, это был «совокупный» «агент-ходок», который должен был посетить интересовавшие Паренсова районы и выяснить наличие в них турецких войск и их состав. Сам Начович, будучи скомпрометирован в глазах турецкого правительства, не мог переправляться на турецкую территорию. Подобный способ постановки задания приводил к большой затяжке по времени, искажению самих инструкций, а ведь следовало еще дождаться ответа. Провал в одном звене срывал всю операцию. Паренсов вскоре убедился в неэффективности системы использования агента («агентов-ходоков», «агентов-маршрутников»). Более того, далеко не все посылаемые агенты на незнакомой местности могли правильно оценить увиденное, разъезды агентов требовали много времени, вследствие чего доставляемые ими данные теряли свою оперативность. Как вспоминал разведчик: «приходилось… вести дело хотя и добросовестно, но, строго говоря, — неудовлетворительно» (Паренсов П.Д. Указ. соч. С. 114).

Посылка «агентов-ходоков» пригодна была в исключительных случаях, «когда нужно было осмотреть на месте что-нибудь существенное, неизменяемое и не переменявшееся», или «когда нужно было, не полагаясь на почту передать что-либо доверенному лицу». Часто приходилось направлять агента-ходока, чтобы дать ответ на конкретный запрос Главной квартиры, например, сколько войска в Силистрии. Для решения поставленной задачи приходилось подобрать лицо, которое согласилось бы взяться за выполнение поставленного поручения, причем этот человек по своему развитию должен был быть способен направиться в заданный пункт и выведать то, что требуется. Затем нужно было еще добраться к заданному месту и благополучно вернуться назад, что было весьма проблематично, так как турецкие кордоны всячески затрудняли переправу через Дунай и вообще перемещение по Болгарии.

Получаемые сведения Паренсов пытался проверять данными, полученными из других источников, в том числе из публикаций местных газет. Полковник всегда очень осторожно относился к румынским источникам, «так как по опыту знал о наклонности румын к преувеличению всяких страхов, в там числе, и сил неприятеля».

Паренсов, организуя разведывательную деятельность и двигаясь вперед на основе проб и ошибок, пришел к пониманию необходимости создания «постоянного наблюдения» за противником через систематическую постоянную агентуру, которая бы действовала непрерывно. Однако такая система требовала значительных денежных затрат, а сумма, выделенная Паренсову на разведку начальником штаба армии, была для этого явно мала. В конце концов он получил разрешение брать взаймы в российском Генконсульстве в Бухаресте по мере надобности деньги, но кредит был ограничен 5000 франков.

7 января 1877 г. к Паренсову явился известный ему до этого времени только по переписке болгарин Церковский (Черковский), уполномоченный собирать сведения о северо-западной части придунайской Болгарии. По словам самого Паренсова, доставленные сведения были «драгоценными». Подобные сведения уже поступали к русскому разведчику, но он не воспринимал их как достоверные. Церковский на основании собранных данных утверждал, что часть турецкой армии, численностью от 30 до 40 тыс. человек, действовавшая против Сербии у Зайчара и Белградчика и находившаяся под командой Ахмеда Эюб-паши, после перемирия, заключенного между Портой и Сербией, стягивается к Видину и Никополю. Причем в самом Видине насчитывалось 7500 человек гарнизона, остальные же части располагались в окрестностях города и в Никополе.