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