Замки замками, однако подросток не забывал и о других обязательных атрибутах профессии фокусника: трюках с картами, лентами и т. п. Но больше всего времени он уделял физической тренировке, развивая гибкость суставов, «качая» мускулы, вырабатывая выносливость. В шестнадцать лет Эрих купил у букиниста толстенный растрепанный том под названием «Мемуары Роберта Гудина, посла, писателя и мага, написанные им самим». На целые месяцы он стал для Вейса своего рода библией, которую он читал и перечитывал, постигая тайны магов и факиров. Насколько юноша увлекся «великим Робертом», говорит хотя бы то, что он выбрал фамилию Гудина в качестве своего сценического имени, прибавив к ней одну лишь букву «и» да заменив имя на Гарри.
Первые шаги Гарри Гудини в цирковом мире были весьма скромными.
Вместе с младшим братом Теодором он выступал с бродячими труппами на провинциальных ярмарках, выставках, благотворительных вечерах, а кульминацией их номера «Братья Гудини — освобождение от оков» был трюк с деревянным ящиком, имевшим выдвижную доску. Во время одного из представлений Эрих Вейс познакомился с совсем еще юной девицей Беатрисой Ранер, нечаянно пролив половину содержимого «волшебной чаши» ей на платье. После того как девушка благосклонно приняла смущенные извинения начинающего фокусника, а потом и сшитое его матерью платье — в качестве компенсации за причиненный ущерб, она вскоре стала его женой и на долгие годы постоянной ассистенткой. Единственное, что омрачало счастье юной пары, так это постоянное безденежье. Хотя Гарри Гудини случалось выступать до двадцати раз в день, а по ночам он часами выдумывал и репетировал все новые и новые фокусы, супруги едва сводили концы с концами. Дело дошло до того, что, будучи на гастролях в Чикаго, Гудини обошел редакции нескольких газет, предлагая за 20 долларов раскрыть секрет своего освобождения от веревок и наручников. Увы, желающих заключить сделку не нашлось.
Как это ни парадоксально, именно неудача подала Гудини идею, осуществление которой стало первым шагом на его пути к славе. «Газетам нужна сенсация, а не просто объяснение фокусов, пусть даже эффектных», — справедливо решил он. Друзья устроили ему знакомство с шефом чикагских детективов Энди Роуаном. После этого Гудини вместе с женой дважды приходил к нему с визитами вежливости в городскую тюрьму. Пока Бесси развлекала светскими разговорами веселого толстяка Роуана, ее муж сумел незаметно познакомиться с тюремными замками. Третий визит Гудини нанес в сопровождении репортеров и фотографов, которым он пообещал продемонстрировать «невозможное»: будучи закованным в наручники, освободиться от них и выйти из запертой тюремной камеры. Удивленный появлением газетчиков, Энди Роуан тем не менее сразу же смекнул, какую выгоду сулит ему предложение фокусника, и охотно принял вызов. Гудини надели наручники и заперли в самый надежный карцер. Прошло несколько минут, и он, как ни в чем не бывало, появился в кабинете шефа детективов. Однако там его ждало разочарование. Пока иллюзионист отсутствовал, репортеры узнали о его предыдущих посещениях тюрьмы и решили, что он просто заранее ухитрился сделать слепок с ключей или замков.
Гудини был не на шутку расстроен провалом своего плана, но решил не сдаваться. Чтобы убедить скептиков репортеров, он предложил повторить «волшебное освобождение». А чтобы ни у кого не оставалось сомнений, его должны были предварительно раздеть донага, тщательно осмотреть да еще наложить на рот гипсовую повязку. Такой трюк действительно мог стать сенсацией, и поэтому решено было повторить все сначала, заперев к тому же одежду Гудини в другую камеру. На сей раз его ждал настоящий триумф: репортеры и сам Роуан были поражены и не могли найти объяснения только что виденному собственными глазами. Гарри Гудини вошел в кабинет полностью одетый, причем не из внутреннего коридора, а из двери, ведущей к уличному входу. На следующий день газеты были полны описаниями невероятного «волшебства», продемонстрированного «магом» Гарри Гудини.