Павел Эдмунд Стшелецкий родился 20 июля 1797 года в Глушине под Познанью в семье мелкого шляхтича Францишека Стшелецкого и Анны Рачиньской. В то время это была территория Пруссии, так что у него было прусское подданство. Он окончил школу в Варшаве и так и не получил высшего образования. В 1816 году Стшелецкий совершил поход в Татры. Примерно в 21 год он пошёл в прусскую армию, где пробыл очень недолго, так как не терпел строгой дисциплины.

Стшелецкий отправился в Италию, где изучал языки и геологию. Там он познакомился с князем и бывшим участником восстания Костюшко Францишеком Сапегой, который предложил ему стать управляющим своего поместья в Царстве Польском. В 1829 году Сапега умер, а у его сына не сложились отношения с управляющим. В следующем году Стшелецкий был вынужден уехать в Великобританию.

О годах, проведённых Стшелецким в Великобритании, почти нет достоверных сведений; вероятно, он углублял свои познания в геологии. В 1834 году Стшелецкий отплывает в Нью-Йорк. Около года он путешествовал по США и Канаде, вёл геологические исследования, знакомился с бытом индейцев. Затем он на два года уехал в Южную Америку, где посетил несколько стран.

Из Вальпараисо в 1838 году Стшелецкий на британском корабле Флай отправился в путешествие по Тихому океану. Он побывал на Маркизских островах, Таити и Гавайях (в то время известных как Сандвичевы острова). Стшелецкий совершил восхождения на Килауэа и Мауна-Лоа, изучал местные языки. На Таити Стшелецкий по приглашению королевы Помаре IV задержался на три месяца. Затем он сел на французский корабль Жюстин и в феврале 1839 года прибыл в Новую Зеландию, а в апреле тот же корабль доставил его в Сидней.

В апреле 1839 г. в Стшелецкий высадился Сиднее. Полгода он блуждал по Австралийским Альпам, проводил съемки и летом, достигнув верхнего Муррея, который он позднее проследил до истока, открыл высокую гору (15 февраля 1840 г.) и поднялся на нее. Величественную вершину, — писал Стшелецкий на родину, — на которую до меня никто не поднимался, с ее вечными снегами и безмолвием, я использовал, чтобы увековечить на этом материке в памяти грядущих поколений дорогое имя, почитаемое каждым поляком — каждым другом свободы… В чужом краю, на чужой земле… я назвал ее горой Косцюшко.

Австралийские географы закрепили это название за высшей точкой материка (2228 м), хотя в 80-х гг. и было окончательно доказано, что Стшелецкий поднялся не на нее, а на соседнюю вершину Снежных гор, ниже на 9 м (Таунсенд, 2219 м).

Перевалив юго-западные отроги Австралийских Альп, Стшелецкий вышел к заливу Уэстерн-Порт, пробираясь через заросли кустарников и рощи эвкалиптов и акаций юго-восточной приморской полосы (Гипсленд), сельскохозяйственные возможности которой он высоко оценил.

В 1842 г. Стшелецкий перешел в Тасманию и был первым геологом, изучившим остров.

В 1845 г. в Лондоне вышло его Физическое описание Нового Южного Уэльса и Вандименовой Земли. На юге Большого Артезианского Бассейна, к северу от хребта Флиндерса, пролегает русло крика (пересыхающей реки) длиной около 250 км, которую австралийские географы назвали Стшелецки-Крик — дань их уважения и признательности одному из крупнейших исследователей Австралии.