Как житель Познанской области, вошедшей после разделов Польши и Венского конгресса в состав Пруссии, Павел служил в прусской армии. Царящая в ней бездумная атмосфера тяготила юношу, жаждущего науки и знания света. Полученный им вскоре офицерский чин обязывал его к дальнейшей воинской службе. Он решил бросить службу, а поскольку ему отказали в увольнении, то в один прекрасный день он попросту уехал из казарм с тем, чтобы больше туда не возвращаться.
Когда военные власти объявили Стшелецкого дезертиром, он уже находился в Италии, где интересовался извержением Везувия и старательно учился. Ведь он прекрасно понимал, что для познания тайн земли необходимо усвоить основы геологии. Кроме того, он изучает языки и проводит целые дни в библиотеках.
Во время одной из экскурсий, посвященных исследованию вулканических явлений, Стшелецкий познакомился с князем Францишеком Сапегой. После многолетних заграничных путешествий Сапега возвращался на родину и предложил молодому соотечественнику должность администратора своих колоссальных имений. Стшелецкий находился в трудном финансовом положении. Полученный от сестры скромный фонд уже истощился. Следовало задуматься о заработке. Хоть и жаль ему было покидать итальянские вулканы, он согласился вернуться на родину, только на этот раз на территорию, отошедшую к России, где ему не угрожало судебное дело за совершенное дезертирство.
После смерти Сапеги он вновь выехал за границу. Сначала изучал в Гейдельберге географию, а затем перебрался в Англию и записался на геологический факультет Оксфордского университета. Получив диплом в 1834 году, он отправляется в десятилетнее путешествие. Пять лет потратил он на посещение обеих Америк и Океании. Был первым до Домейко поляком, прошедшим через перевал Успальята в Андах. Высаживался также на Гавайях, Таити и Новой Зеландии. Оттуда путь вел в Австралию.
Стшелецкий сам добывал средства для путешествий, продавая европейским музеям те редкие этнографические материалы, которые ему удавалось найти. Полученными таким образом деньгами он оплачивал стоимость своих поездок.
Трехлетнее странствие по обеим частям Америки позволило ему посетить Нью-Йорк, Бостон, Филадельфию, Вашингтон, совершить поездку по реке Гудзон, осмотреть Ниагарский водопад и оттуда отправиться в Канаду. Затем он побывал на Антильских островах, в Мексике, а на обратном пути совершил плавание по Миссисипи и Огайо до Цинциннати и Балтимора. После восемнадцати месяцев пребывания в Северной и Центральной Америке он покидает Соединенные Штаты, чтобы отправиться в Бразилию.
В высланном из Австралии письме Адине Турно он так описывает свое пребывание в Южной Америке:
Стшелецкий был первым европейским натуралистом, изучавшим природу Нижней Калифорнии.
В апреле 1839 года польский путешественник прибыл на корабле в австралийский порт Сидней и на следующий день добился аудиенции у губернатора.