Фридрих Великий, восстанавливая растерзанную войнами Пруссию, объявил свободу вероисповедания, и ко времени его смерти 20 процентов населения Пруссии составляли иммигранты. Потемкин пошел еще дальше: он стал помещать объявления в иностранных газетах и создал сеть вербовщиков по всей Европе. «Европейские газеты, — объяснял он Екатерине, — не нахвалятся новыми поселениями в Новороссии и на Азове». Узнав о привилегиях, жалованных греческим и армянским поселенцам, «их оценят по достоинству».

Еще одна его идея, опередившая время, — использование для набора колонистов русских посольств за границей. Впрочем, этой деятельностью он с увлечением занимался с первых дней своего возвышения еще в середине 1770-х годов, когда обустраивал Моздокскую линию на Северном Кавказе. Идеальные поселенцы, по мысли Потемкина, должны были в мирное время пахать, сеять, торговать и работать на мануфактурах, в военное — бить турок.

Первыми потемкинскими поселенцами стали греки, нанятые Алексеем Орловым моряками в его эскадру в 1769 году, и крымские христиане. Греки обосновались сначала в Еникале, крымские жители —в Мариуполе. Потемкин строил для них школы и больницы; после присоединения Крыма он сформировал из греков несколько полков и переместил их в Балаклаву, но продолжал развивать Мариуполь именно как греческий город. В 1781 году азовский губернатор докладывал ему, что уже имеется четыре церкви, у греков есть собственный суд, а торговля процветает. Для армян Потемкин позднее основал Нахичевань, в нижнем течении Дона, и Григорио-поль на Днестре.

Не менее усердно Потемкин искал поселенцев внутри империи, привлекая помещиков с крестьянами, отставных солдат, бедных сельских священников. Бежавшим за пределы империи крепостным, раскольникам и казакам, укрывшимся в Польше или Турции, он обещал прощение и свободу. Семьи и целые деревни переезжали на новые места — или возвращались на родину. Считается; Что к 1782 году Потемкин удвоил население Новороссии и Приазовья.

После присоединения Крыма кампания пошла еще интенсивнее; За годы крымских волнений 1770-х — начала 1780-х годов мужское население полуострова сократилось до 50 тысяч человек. Потемкин утверждал, что это — одна десятая необходимого. Приглашая поселенцев, сведущих в разных областях хозяйства, он сам решал, кому платить какие налоги и сколько, какие земельные наделы должны получать вновь прибывшие. Обычно они освобождались от уплаты податей — в начале кампании на полтора года, потом на шесть лет.

Особенно охотно отзывались крестьяне южной Европы. В 1782 году под Херсон прибыли корсиканцы — 61 семья. В начале 1783 года Потемкин договаривался об отправке корсиканцев и евреев с герцогом де Крийоном. Но потом он решил, что «нет нужды увеличивать число поселян» и можно ограничиться теми, которых «уже прислал граф Мочениго» (русский посол во Флоренции). Некоторые желающие перебраться в Россию сами писали князю. Например, двое греков, Панаио и Алексиано, просили разрешить приехать со своими семьями «с Архипелага [...] и основать колонию, которая будет больше, чем корсиканская». Агенты по найму получали по 5 рублей с колониста. Некоторые из агентов, разумеется, были мошенниками, а многие помещики воспользовались кампанией как прекрасной возможностью избавиться от всякого сброда. Потемкин понимал это.

Наряду со случайными людьми ему удалось привлечь и таких добросовестных и работящих поселенцев, о каких только мог мечтать устроитель нового края, — например, членов секты меннонитов из Данцига. Меннониты ставили условием своего переселения право строить собственные церкви и не платить налоги в течение десяти лет. Агент Потемкина Георг Траппе гарантировал им, что их условия будут соблюдены и по прибытии на место они получат дома и подъемные средства.