Ещё до Юлиана, вероятно в 1231—1232 годах, на поиски восточных венгров, которые «всё ещё остаются в заблуждении неверия», отправлялись четыре венгерских доминиканца. Трое из них погибли, но четвёртому, Отто, удалось получить сведения о пути к Великой Венгрии и вернуться на родину после трёхлетних странствий. Несмотря на то, что Отто через восемь дней после возвращения скончался, он успел поделиться этими сведениями с братией.
В первые дни мая 1235 года Юлиан с тремя другими доминиканцами пустился в путь из монастыря, расположенного, вероятно, в Буде или Пеште. Они ехали с охранной грамотой и на средства князя Белы (будущего короля Белы IV). Монахи были облачены в мирское платье, кроме того, они отпустили бороду и волосы, чтобы не выделяться среди «язычников». Следуя через Секешфехервар, Печ, Белград, Ниш, Софию, Филиппополь и Адрианополь, доминиканцы за месяц достигли Констанинополя. После 33 дней плавания на корабле вдоль берегов Малой Азии монахи оказались в Матархе (Тмутаракань). Ожидание попутчиков затянулось на 50 дней, и лишь в конце августа путешествие продолжилось. Пройдя вдоль реки Кубани, от её изгиба они повернули на северо-восток и в конце сентября достигли страны аланов.
Два спутника Юлиана решили вернуться в Венгрию «из-за боязни татар, которые по слухам были близко». Оставшиеся Юлиан и Герард провели 6 месяцев, практически не имея средств к пропитанию, и, видимо, не ранее 20 марта 1236 года отправились дальше на север.
После 37 дней труднейшего пути через пустыню монахи достигли страны Вела (вероятно, на берегах реки Уил). Они пожили некоторое время в городе Бунда, а затем перешли в другой город, где 7 мая брат Герард скончался. Сам Юлиан, нанявшись слугой, вместе со своим хозяином отправился в Великую Булгарию. Там он повстречал женщину, которая указала ему путь в искомую страну. На берегах неизвестной реки Юлиан нашёл людей, язык которых «совершенно венгерский: и они его понимали и он их». Будучи принят радушно, доминиканец около месяца прожил среди них.
20 июня Юлиан пустился в обратный путь. Он прошёл через мордовскую землю и примерно в середине августа достиг Нижнего Новгорода. Затем миновал Владимир, Рязань, Чернигов, Киев и Галич, а 27 декабря перевалил Карпаты. В начале 1237 года Юлиан, вероятно, был в Буде с докладом королю Беле IV, а весной того же года — в Риме, где его донесение папе Григорию IX записал монах Рихард.
Осенью 1237 года Юлиан вновь отправился в путь. Достигнув восточных пределов Руси, он узнал, что и Великая Венгрия и Булгария уже разорены монголами. От беженцев Юлиан узнал, что монгольские войска сосредоточены вблизи границ русских княжеств и готовы к вторжению зимой, когда реки и болота замёрзнут. На обратном пути на родину Юлиан побывал в ещё не затронутом войной Суздале, где был принят князем.
Путешествия Юлиана описаны в двух сочинениях — Relatio fratris Ricardi, докладе, составленном с его слов монахом Рихардом (Richardus), и Epistula de vita Tartarorum («Письмо о жизни татар») — собственном отчёте Юлиана Сальвио де Сальви (Salvio de' Salvi), архиепископу Перуджи, папскому легату в Венгрии. Сочинения являются важными источниками по истории монгольского вторжения в Волжскую Булгарию. Историками признаётся высокая степень достоверности сообщённых Юлианом сведений, так как они представлены в закрытых документах делового характера.
Описанию путешествий Юлиана посвящена историческая повесть В. В. Каргалова «Колумб Востока». Повесть написана в соответствии с источниками, местами автор следует тексту отчётов Юлиана буквально. Авторская фантазия проявляется в описании характера самого Юлиана. В начале повести он предстаёт юным монахом, мечтающим о путешествии в неведомые страны, откуда, по преданию, вышли предки венгров и где живут их сородичи. Эти сородичи представлялись Юлиану «людьми кроткими и доверчивыми», он желал идти к ним «с открытым сердцем, как к братьям». Однако, монастырское начальство, отправлявшее Юлиана в путь, трактовало восточных венгров как заблудших и погрязших в грехах язычников, которых нужно приобщить к истинной католической вере силой либо хитростью.