Павел Эдмунд Стшелецкий родился в Глушине под Познанью в семье мелкого шляхтича Францишека Стшелецкого и Анны Рачиньской. В то время это была территория Пруссии, так что у него было прусское подданство. Он окончил школу в Варшаве и так и не получил высшего образования. В 1816 году Стшелецкий совершил поход в Татры. Примерно в 21 год он пошёл в прусскую армию, где пробыл очень недолго, так как не терпел строгой дисциплины, и дезертировал.
Тогда же у Стшелецкого завязался роман с пятнадцатилетней дочерью полковника Александриной (Адиной) Турно. Влюблённые хотели вместе бежать, но отец девушки раскрыл их замысел. Стшелецкому пришлось покинуть Познань. Он отправился в Италию, где изучал языки и геологию. Там он познакомился с князем и бывшим участником восстания Костюшко Францишеком Сапегой (), который предложил ему стать управляющим своего поместья в Царстве Польском. В 1829 году Сапега умер, а у его сына не сложились отношения с управляющим. В следующем году Стшелецкий был вынужден уехать в Великобританию.
О годах, проведённых Стшелецким в Великобритании, почти нет достоверных сведений; вероятно, он углублял свои познания в геологии. В Великобритании он начинает добавлять к своему имени титул графа (англ. Count), хотя у него не было на это никаких прав. В 1834 году Стшелецкий отплывает в Нью-Йорк. Около года он путешествовал по США и Канаде, вёл геологические исследования, знакомился с бытом индейцев. Затем он на два года уехал в Южную Америку, где посетил несколько стран. Из Вальпараисо в 1838 году Стшелецкий на британском корабле «Флай» отправился в путешествие по Тихому океану. Он побывал на Маркизских островах, Таити и Гавайях (в то время известных как Сандвичевы острова). Стшелецкий совершил восхождения на Килауэа и Мауна-Лоа, изучал местные языки. На Гавайях до него дошло письмо Адины Турно, с которой он в дальнейшем поддерживал переписку. На Таити Стшелецкий по приглашению королевы Помаре IV задержался на три месяца. Затем он сел на французский корабль «Жюстин» и в феврале 1839 года прибыл в Новую Зеландию, а в апреле тот же корабль доставил его в Сидней.
По приезде в Австралию Стшелецкий начал геологические исследования, которые растянулись на четыре года. За это время он объездил большую часть континента и Тасманию. Уже в год приезда он нашёл золото около городков Хартли Вейл и Батхёрст в Новом Южном Уэльсе, но по просьбе губернатора Гиппса сохранял эту новость в тайне, чтобы не допустить волнений каторжан. Через 12 лет золотые прииски были открыты в Виктории, что привело к золотой лихорадке, которая обернулась крупными социальными потрясениями. В настоящее время Стшелецкий считается наиболее вероятным кандидатом на звание первооткрывателя золота в Австралии.
15 февраля 1840 года Стшелецкий покорил высочайшую вершину Австралии и дал ей название Косцюшко в честь национального героя Польши. После этого Стшелецкий со своими спутниками проделал изнурительное пешее путешествие по местности, которую он назвал Гиппсленд в честь губернатора Гиппса. Путешествие окончилось скандалом, так как Стшелецкий объявил себя первопроходцем этого маршрута, не зная о том, что незадолго до того по нему прошёл Энгус Макмиллан.
Стшелецкий покинул Австралию в 1843 году. Результатом экспедиции по Австралии стала книга «Физическое описание Нового Южного Уэльса и Земли Ван-Димена» (Physical Description of New South Wales and Van Diemen’s Land). За неё Стшелецкий был удостоен медали Королевского географического общества. В этом же году ему было даровано британское подданство.
Во второй половине 1840-х годов в Ирландии разразился «великий голод». В январе 1847 года Стшелецкий был назначен агентом по распределению продовольствия в графствах Мейо и Слайго. Он самоотверженно работал, даже когда в апреле заболел брюшным тифом. В том же году он был повышен до комиссара в Дублине. За заслуги в борьбе с голодом Стшелецкий был произведён в рыцари Ордена Бани.
Во время Крымской войны Стшелецкий участвовал в деятельности комитета помощи, созданного Флоренс Найтингейл, а после войны посетил Крым вместе с дипломатом Ричардом Лайонсом. В последние годы жизни Стшелецкий был удостоен многих почестей: он стал членом Королевского географического общества (1853), Лондонского королевского общества (1853), получил почётную степень доктора гражданского права Оксфордского университета (1860), был награждён орденом Святого Михаила и Святого Георгия (1869). Стшелецкий умер в Лондоне в 1873 году.
В Австралии:
В Канаде: