С момента бегства из родного Палермо началась его карьера мелкого афериста. Он скитался по городам Италии, где, используя навыки рисовальщика, подделывал завещания и векселя, а с помощью полученных от отца-травника знаний по целительству и фармакологии и составлению всевозможных порошков, мазей, отваров, настоек и бальзамов из целебных трав изготавливал и продавал приворотные зелья, промышлял мошенничеством, продавая простакам чудесные амулеты. Затем его следы затерялись на три года, до 1766 года: возможно, в этот период одаренный разными талантами молодой человек и впрямь побывал на Ближнем Востоке и в Африке, где обрел наставника, названного им условным именем "Альтотас", и многому научился.
Но прежде чем отправиться странствовать на Восток, Бальзамо решил навестить свою двоюродную бабушку и крестную мать, жившую близ Мессины — Винченцу Калиостро, дочь Маттео Мартелло. Увы, она уже умерла, а наследство было поделено между родственниками. Тогда Бальзамо присвоил себе ее звучную фамилию и с этого времени стал называться Калиостро.
Новоиспеченный Калиостро и его наставник побывали в Египте. Там они выделывали окрашенные под золото ткани, пользовавшиеся большим спросом; Альтотас, по-видимому, обладал некоторыми познаниями в области химической технологии. В египетской Александрии Джузеппе близко сошелся с уличными факирами. Он овладел приемами гипноза, изучил магические формулы, научился довольно сложным фокусам, собрал коллекцию экзотических предметов. С Альтотасом он побывал в Мемфисе, Каире, посетил Мекку. Из Египта они перебрались на остров Родос, затем на Мальту, где, по одной из версий, назвавшегося своим настоящим именем Джузеппе Бальзамо принял сам гроссмейстер, португалец Пинто да Фонсека, известный своим увлечением алхимией. В одной из башен гроссмейстерского дворца Пинто оборудовал и оснастил лабораторию, куда допустил Бальзамо. Тесные отношения Калиостро с орденом и благосклонность его Великого магистра могут объясняться тем, что на протяжении веков многие члены семьи Бальзамо становились мальтийскими рыцарями. Но если, как впоследствии утверждала Папская курия, предками Калиостро со стороны отца были евреи, значит, среди них не могло быть мальтийцев, ибо для вступления в орден следовало доказать, что в роду на протяжении двухсот лет не было ни магометан, ни евреев… Однако в любом случае фамилия Бальзамо рыцарям, защищавшим крест, была известна, ибо фамилия эта была достаточно распространенной в Италии: среди дворянства насчитывалось по крайней мере шесть семейств Бальзамо, и три из них — на юге страны.