После возвращения из-за границы в 1859 г. Налбандян уже не мог сотрудничать в журнале Назарянца. Между ними возникли серьезные расхождения. Назарянц по существу пожертвовал Налбандяном ради спасения своего журнала. Он или не публиковал его произведений, в которых выражались откровенно революционные взгляды, или безжалостно кромсал их. Налбандян сделал попытку создать свой печатный орган. На этот раз уже в Петербурге, через своего последователя М. Будагяна. М. Будагян официально обратился в соответствующие органы русского правительства за разрешением издавать армянскую газету, но получил отказ.
Налбандян оказался в тяжелых условиях: царская цензура лишила его слова, он не мог публично выражать свои идеи. Однако он не сдавался. Главным образом для достижения своей основной цели — создания нового армянского печатного органа в России — в мае 1860 г. Налбандян успешно защитил кандидатскую диссертацию по филологии. Диссертация эта по своему научному уровню слаба и явно ниже возможностей автора, но с ее помощью Налбандян достиг своей цели: кандидатская степень давала ему право на самостоятельное ходатайство об издании своего печатного органа, что он и намерен был сделать. Однако обстоятельства сложились иначе. Жители Новой Нахичевани, несмотря на отчаянное сопротивление Г Айвазовского и его окружения, выбрали Налбандяна своим уполномоченным представителем для получения завещанной армянскими богачами в Индии суммы, предназначавшейся для сооружения в городе школ и других культурных учреждений. Налбандян охотно принял это предложение, так как он получал возможность по пути в Индию побывать в важнейших армянских центрах Закавказья и Турции, а также посетить своих друзей в европейских странах, что было очень важно для упрочения связей революционно-демократических сил армянского народа с деятелями русского и итальянского освободительного движения — с группой А. И. Герцена и Н. П. Огарева, с Дж. Гарибальди и Дж. Мадзини.
Эта поездка Налбандяна вызвала особую тревогу в стане армянских крепостников. Журнал «Мясац Ахавни» писал, что Налбандян отправился в путешествие, чтобы поднять армянский народ против существующего строя в России и Турции. Константинопольский монах О. Чамурчян в своем журнале «Еревак» и в специальных брошюрах открыто обвинял Налбандяна в революционных взглядах. Несмотря на злобную кампанию Г. Айвазовского, О. Чамурчяна и их сторонников, в армянских демократических кругах Закавказья, Турции и Западной Европы Налбандян всюду встречал глубокое сочувствие и понимание. Проезжая через Закавказье, он установил связь с демократическими кругами в Тифлисе, побывал в Араратской долине, где предметом его пристального внимания было положение армянского крестьянства. В Константинополе Налбандян организовал подпольную революционно-демократическую организацию под названием «Партия молодых», руководителями которой стали также А. Свачян (редактор демократической газеты «Мегу»), С. Тагворян и др. «Партия молодых» возглавила национально-освободительную борьбу армянских трудящихся Турции.
Обстоятельства сложились так, что для получения визы на поездку в Индию Налбандян должен был прибыть в Лондон. По пути в Лондон он побывал в некоторых городах Италии и Франции. В Италии Налбандян стал очевидцем народного торжества в связи с победами волонтеров Гарибальди. В письмах к А. Свачяну, описывая ликование простого народа Италии, он выражает убеждение, что путь, избранный итальянским народом, является тем путем, на котором только и возможно национальное освобождение каждого народа. В Генуе Налбандян интересуется польскими революционными организациями и добровольческими формированиями в отрядах волонтеров Гарибальди. В Париже он встречается со своим старым другом С. Восканом, а также с И. С. Тургеневым, в Лондоне Герцен и Огарев на этот раз принимают его как соратника. Здесь он знакомится с М. А. Бакуниным и с польским революционным демократом, сотрудником и издателем «Колокола» С. Тхоржевским, с которым в дальнейшем ведет переписку. Во время этой поездки Налбандян установил связь с Гарибальди и Мадзини, о чем свидетельствует письмо члена «Партии молодых» С. Тагворяна. С Гарибальди в эти годы, как известно, пытался установить связь и Н. Г. Чернышевский.