Вскоре Йорк понял, что его рослый племянник, как отмечал один из современников, был парнем "великого духа и смелого мужества, а также природной твердости тела", который больше подходил для жизни в приключениях, чем для меркантильной карьеры. В 1553 году он устроил так, что юный Фробишер, еще подросток, присоединился к экспедиции на Золотой берег Африки, которую он организовывал вместе с несколькими инвесторами "Мистерии", включая сэра Джорджа Барна, старшего.
Йорк верно оценил своего племянника. Фробишер пережил свое первое плавание в Гвинею, хотя большинство членов экипажа, включая капитана, погибли под африканским солнцем. В следующем году он присоединился к обратному путешествию под руководством Джона Лока. Вскоре после достижения Золотого берега капитан Лок попытался заключить коммерческую сделку, но местный африканский король потребовал от англичан обещания доброй воли, прежде чем начать торговлю: а именно, один из членов команды корабля должен был остаться в их деревне, чтобы обезопасить себя от теневых сделок. Фробишер, которому еще не исполнилось и двадцати, вызвался добровольцем и был передан под опеку вождя. Однако вскоре все пошло наперекосяк. Африканские торговцы открыли стрельбу, и англичане, решив, что надвигается беда, поспешили прочь. Лок оставил Фробишера позади, похоже, даже не оглянувшись, поскольку тот не вернулся и не предпринял никаких попыток спасти своего юного подопечного.
Африканцы в конце концов передали Фробишера португальцам, которые перевезли его в грозную крепость Сан-Жоржи-да-Мина, торговый форпост Португалии в Западной Африке. Там, согласно более поздним показаниям Фробишера, его продержали в заточении девять месяцев, хотя вскоре он оказался полезен своим похитителям. Его регулярно отправляли в леса для обмена "коз, домашней птицы и других продуктов" с местными африканскими племенами, поскольку португальцы "не могли, рискуя жизнью, делать этого". Фробишер пережил этот опыт, и португальцы в конце концов отправили его обратно в Англию после короткого заключения в лиссабонской тюрьме.
В течение следующих двадцати лет Фробишер с большим энтузиазмом продолжал идти по пути, который определил для него дядя. Он участвовал в бесчисленных плаваниях и даже совершал пиратские акты, за которые проводил в тюрьме все больше времени. Однако ни одно тюремное заключение не длилось долго, и, похоже, он заслужил одобрение ряда самых влиятельных деятелей Англии, включая Уильяма Сесила. Как отметил Майкл Лок, Фробишер пользовался "добрым расположением" не только Сесила, но и "других членов достопочтенного Тайного совета Ее Величества". Почти наверняка это одобрение было связано с его работой в качестве правительственного шпиона и капера - своего рода лицензированного пирата. В классическом случае браконьера, превратившегося в егеря, его наняли для поиска пиратов и контрабандистов, перевозящих запрещенные товары в Ла-Манше.
Но именно в те дни, когда Фробишер провел в лиссабонской тюрьме, он впервые задумал добраться до Катая через Северо-Западный проход. По-видимому, один из его товарищей по заключению, португальский моряк, рассказал , что он "прошел" через ледяной морской путь, и поделился с Фробишером секретами этого маршрута. В течение следующих нескольких лет, как он позже рассказывал одному из своих офицеров, он обсуждал эту идею со "своими частными друзьями" и сделал "множество предложений" "разным купцам нашей страны" предпринять попытку пройти на северо-запад. Однако, несмотря на свою настойчивость, Фробишер не смог вызвать большого интереса у деловой элиты Лондона. В результате, как отмечал Джордж Бест, сын переводчика Мусковитской компании и официальный летописец плавания, Фробишер устал от купцов, которые требовали "уверенной, определенной и настоящей выгоды". Они были осторожны и консервативны, готовы рисковать, но не безрассудно. Учитывая неудачу попыток достичь Катая северо-восточным путем, это неудивительно.
Однако Фробишер не сдавался. Мореплавание по Северо-Западному проходу рассматривалось - особенно англичанами - как последний великий вызов эпохи. Фробишер понимал, что это "единственное дело в мире, которое еще не сделано, благодаря которому выдающийся ум может стать знаменитым и удачливым". Итак, в конце 1574 года, устав от отказов купцов, он наконец обратился "ко двору (откуда, как из основания нашего содружества, все добрые дела получают свой главный прирост и поддержку)". Там он "открыл многим великим сословиям и ученым людям замысел и сумму своего завещания".