Павел Эдмунд Стшелецкий (Стржелецкий) родился 24 июня 1797 года в Глушине под Познанью в семье шляхтича. От родителей впитал культ Тадеуша Косцюшко, под командованием которого служил его отец.

"Как иные люди родятся с полнокровным или черепашьим темпераментом, - писала польская поэтесса Нарцисса Жмиховская, печатая пространные воспоминания о жизни и деятельности своего далекого кузена, -так, несомненно, Стшелецкий родился с темпераментом путешественника. Он имел все необходимые для путешественника качества: крепкое здоровье, бесстрашную отвагу, хладнокровие при опасности, ловкость гимнаста, сопутствующую большой мускульной силе, необходимую в нужде закалку - он со спартанским безразличием переносил голод, холод и жару. А, кроме того, у него была душа бродяги Он, как бедуин или киргиз, нуждался в перемене мест, в движении в пространстве".

Следующие годы - это сплетение самых удивительных приключений. Период Варшавского княжества молодой Павел проводит в варшавских школах. В 1816 году девятнадцатилетний юноша выезжает в Краков. Неизвестно откуда он достает средства к существованию, вернее всего бедствует, но, несмотря на это, совершает экскурсию в горы - в тогда еще малоизвестные Татры. Это можно считать первыми проявлениями "души бродяги" , о которой писала Нарцисса Жмиховская.