Прослышав, что Такэда Сингэн и Уэсуги Кэнсин нанимают ниндзя, он решил наняться к кому-либо из них на службу. Сначала Дандзо отправился во владения Уэсуги. Прибыл он к замку Уэсуги по видом бродячего фокусника и на рыночной площади призамкового городка принялся демонстрировать свое магическое искусство.
Как рассказывает легенда, он привел на площадь большого быка и на глазах у всех собравшихся во мгновение ока его проглотил. Все зрители были поражены, но один человек, забравшийся на высокую сосну, что была по соседству, начал подшучивать: «Обман! Обман! Если посмотреть отсюда, он просто уселся быку на спину!» Като Дандзо сильно рассердился, взял в руки саженец тыквы-горлянки, на котором было всего лишь два листика, махнул на него веером и, как ни странно, лоза стала постепенно удлиняться, и прямо на глазах у зрителей на ней зацвел цветок тыквы-горлянки. Когда все зрители в изумлении пораскрывали рты, Като неожиданно выхватил короткий меч и одним ударом отсек чашечку тыквы-горлянки. Как только он это сделал, отрубленная голова шутника шлепнулась на землю. Зрители, пораженные и напуганные этим необычайным искусством, тут же бросились врассыпную.
По городу поползли противоречивые слухи о таинственном и страшном пришельце, а он сам тем временем явился к Какидзаки Идзуми-но Ками, приближенному князя Уэсуги, заявил, что он лучший ниндзя во всей стране, и попросил представить его князю. Самурай потребовал у Дандзо, чтобы тот продемонстрировал свое искусство, и тогда Летучий Като показал ему свой невероятный прыжок. Самурай пришел в восхищение от столь великого таланта и немедленно доложил о своей «находке» Уэсуги.
На аудиенции у князя Дандзо вел себя вызывающе и вновь похвастал, что равного ему по мастерству ниндзя во всем свете не сыскать. Тогда Кэнсин нахмурил брови и сказал: «Ну, ежели ты такой мастер, покажи нам свое мастерство. Есть у меня старый вассал Наоэ Ямасиро-но Ками. В его усадьбе хранится драгоценная алебарда. Если ты сможешь ее сегодня ночью украсть, я возьму тебя на службу и назначу большое жалованье».
Задача Дандзо была поставлена не из легких. Огромный дом Наоэ, защищенный высокими стенами, окружал широкий ров. Многочисленные сторожа неустанно вглядывались в темноту, и подобраться к усадьбе незамеченным не было никакой возможности. Вокруг усадьбы рыскал огромный свирепый волкодав по кличке Мурасамэ, способный учуять любого чужака за сотни метров и прославившийся тем, что как-то на охоте в одиночку загрыз дикого кабана. Кроме того, все комнаты в доме были ярко освещены, и в них постоянно находились десятки слуг.
И все же Дандзо решил во что бы то ни стало прокрасться ночью в дом Наоэ. Воспользовался он при этом отнюдь не магией, а вполне «посюсторонними» методами — обычными уловками ниндзя. Злобному Мурасамэ он подсунул колобок заранее припасенного и отравленного риса-якимэси, после чего псина, отведав «лакомства», тут же издохла. Затем Дандзо могучим прыжком преодолел ров — не зря же его прозвали «Летучим»! При помощи лазательных когтей (сюко) он взобрался на стену и беззвучно, как кошка, спрыгнул во двор.
Так как дело было уже под утро, у охранников, которые чересчур рьяно сторожили усадьбу вечером и ночью, к этому времени уже глаза слипались. Поэтому ниндзя даже решил немного покуражиться — он не только утащил драгоценную нагинату, но еще и усадил на спину сладко проспавшую все время его ночных похождений одиннадцатилетнюю прислужницу жены Наоэ и в таком виде — с алебардой в руках и девчонкой за спиной — явился во дворец Уэсуги.
Все были поражены невероятным мастерством ниндзя. И даже Кэнсин застонал от восторга. Он прекрасно понимал, что этот человек мог оказаться подарком судьбы в борьбе с Такэдой, и уже предвкушал, как при помощи Дандзо отправит своего заклятого врага на тот свет.
Правда, было тут одно «но». «Как бы Като Дандзо не был подослан врагами?» — думал князь. А тут еще оскорбленный Наоэ стал нашептывать ему, что Дандзо — человек совершенно неизвестный, прошлое его темно, и уж очень его неожиданное появление здесь напоминает уловку врага. Долго раздумывал Кэнсин. И в итоге это одно «но» перевесило все таланты великого синоби. Он подозвал к себе начальника охраны Оникодзиму Сётаро и шепнул ему на ухо приказ немедленно прикончить опасного чужака.
Однако Дандзо был не дурак. По каким-то признакам он разгадал план князя и решил дать деру пока не поздно. Правда, охранников в замке было слишком много. Тут-то и пригодилось ниндзя его магическое (фокусническое или гипнотическое) искусство. Обращаясь ко всем присутствующим, он сказал: «Ну что ж, господа. Я хочу показать вам кое-что интересное». С этими словами, Дандзо подозвал к себе похищенную девочку и стал вынимать у нее изо рта одну за другой кукол размером в 3 суна каждая. Когда он извлек их уже штук 30, куклы тали забавно пританцовывать. Все зрители, словно завороженные, уставились на фантастическое зрелище. А хитроумный Като Дандзо тем временем беспрепятственно выбрался из недружелюбного замка.