Партийной работе Нгуен отдавал все свободное время. Хотя ему уже перевалило за 30, он еще не преподнес ни одной девушке, как того требовала древняя вьетнамская традиция, красный шелк, чтобы бог бракосочетания Лунный старец навеки связал его с избранницей красной шелковой нитью. Может быть, в родной деревне Лотосов оставалась его любимая девушка, которую в соответствии с феодальными обычаями вьетнамской деревни с отроческих лет по взаимному уговору семей предназначили ему в жены. Но с тех пор много воды утекло. Для односельчан он был без вести пропавший. Даже если существовал у его отца с какой-нибудь семьей уговор, он потерял свою силу за давностью лет. На чужбине же найти достойную спутницу жизни оказалось непросто. Частые переезды из одной страны в другую, аскетический образ жизни профессионального революционера, законы конспирации — все это отодвигало устройство личных дел на задний план.
Так он и не успел вовремя жениться, прожив всю жизнь холостяком.
Работая в комиссии ЦК, Нгуен часто встречался с прогрессивно настроенной молодежью из различных французских колоний — алжирцами, тунисцами, мадагаскарцами, мартиниканцами. Среди молодых людей постепенно зреет идея создания единой организации. В июле 1921 года, собравшись на чьей-то квартире, они принимают решение о создании Союза колониальных народов. Нгуена избирают в руководящий комитет. В уставе союза, разработанном Нгуеном, указывалось, что союз ставит перед собой цель объединить представителей французских колоний, живущих во Франции, вести среди них агитационно-пропагандистскую работу, добиваться их сплочения в общей борьбе за национальное освобождение. В первые же дни в союз вступили 200 человек, в том числе две организации — Ассоциация вьетнамских патриотов и Мадагаскарский союз борьбы за права человека.
Одним из активистов союза и близких друзей Нгуена стал уроженец Антильских островов адвокат Блонкур. Через полвека он вспоминал об этих днях: «Нгуен регулярно посещал собрания и митинги, проводившиеся союзом. Работая с ним, я убедился, что он беззаветно предан идее борьбы за освобождение народов колоний, причем не только своей родины — Вьетнама, но всех угнетенных на земле. У него была несокрушимая вера в окончательную победу. Он считал, что для национального освобождения нет иного пути, кроме революции. У меня сложилось убеждение, что мысль о борьбе за национальное освобождение всегда владела его сознанием, определяя всю его жизнь. Я помню, как однажды, узнав о варварских репрессиях французских колонизаторов в Дагомее, он возмутился до глубины души и страдал так, будто все это произошло во Вьетнаме, с его народом. Он был в полном смысле гуманистом и интернационалистом».
Активно сотрудничая в партийных газетах, Нгуен хорошо понимал значение печати для революционной пропаганды. Он выдвинул идею создания союзом собственной газеты. Решили назвать ее «Пария» — это слово как нельзя более точно, по мнению Нгуена и его друзей, отражало то положение, в котором находились угнетенные и униженные народы колоний. Нгуену, как единственному из активистов союза, уже довольно опытному журналисту, поручили редактирование и издание газеты.
Нгуен съездил к Анри Барбюсу и попросил взять шефство над «Парией». В тот период Барбюс стоял во главе созданной по его инициативе Международной лиги прогрессивных писателей «Кларте». В нее входили такие выдающиеся деятели литературы, как Анатоль Франс, Бернард Шоу, Эптон Синклер, Рабиндранат Тагор и другие. Барбюс живо откликнулся на просьбу Нгуена и даже выделил для редакции газеты комнату в здании, где размещался секретариат «Кларте».
Первый номер «Парии» вышел 1 апреля 1922 года. Название газеты, которая имела лишь одну полосу небольшого формата, было написано на трех языках — французском, арабском и китайском, что подчеркивало ее интернациональный характер. В приветствии, обращенном редакцией к читателям, говорилось, что это первая газета, которая выступает от имени трудящихся всех французских колоний.
Распространение «Парии» потребовало большой изобретательности. Поначалу Нгуен и его друзья отсылали газеты почтой по официальным адресам в Индокитай, в Африканские колонии, в Вест-Индию. Однако, узнав, что они практически все конфискуются местной полицией, стали договариваться с моряками, которые тайком провозили газетные листки в портовые города французских колоний. Часть экземпляров распространяли в Париже среди эмигрантов и вьетнамских рабочих. Хотя большинство рабочих не умело читать, они охотно покупали газету, которая, как разъяснял им Нгуен, писала о произволе колонизаторов во Вьетнаме, и просили французских рабочих почитать им. «Пария» продавалась также в парижских киосках, находившихся под контролем ФКП. Больше всего экземпляров удавалось Нгуену распространять на рабочих митингах. Он молча раздавал газетные листки участникам митинга, затем поднимался на трибуну и говорил: