הוריו של קרוגר, כמו גם הוא עצמו, היו עד לשלהי שנות ה-30 של המאה ה-19 נתינים בריטים של מושבת הכף. במצב זה עמדה רוב אוכלוסיית המושבה, אשר היו אפריקאנרים ממוצא הולנדי המצויים תחת שלטון בריטי אשר נתפס בעיניהם כזר. עם זאת, אף על פי שרוב האוכלוסייה כמו גם משפחת קרוגר לא רחשו כבוד רב לשלטונות, הם השלימו בדרך כלל עם המרות הבריטית על הארץ. על מנת לבסס את אחיזתם, הבריטים בתורם ניסו כל העת לרכוש את אמונם של האפריקאנרים. עם זאת, תוך מספר שנים היחסים בין הצדדים עלו על שרטון. תהליך זה היה בעיקר תולדה של צעדים בריטיים אשר נתפסו בעיני האפראקנרים כהתערבות בוטה בענייניהם הפרטיים, וכזאת הייתה ההחלטה הבריטית לבטל את העבדות ברחבי המושבה בשנת 1833. עד מהרה האפריקאנרים תפסו את השלטון הבריטי כרודני, וחשו געגוע לימי השלטון ההולנדי. במקביל החלו קולות של מרד להישמע בקרב האוכלוסייה. עם זאת, לנוכח כוחה הרב של האימפריה הבריטית, הבינו האפריקאנרים שכל ניסיון לעימות ישיר עמה נידון לכישלון. ברם, התגבשה בקרבם יוזמה מרחיקת לכת על פיה מוטב שהאפריקאנרים ינטשו את מקום מגוריהם, יעזבו את גבולות מושבת הכף ויתחילו לנוע מזרחה אל תוך פנים היבשת, שם הם יקימו רפובליקות ריבוניות, וינהלו את חייהם באורח עצמאי וללא התערבות זרה. כאשר הם שואבים השראה דתית ממסעות בני ישראל במדבר היוצאים מחיי עבדות במצרים בחפשם אחר ארץ ריקה וטובה להתיישב בה, וכן השראה מהמהפכה האמריקנית האנטי-בריטית אשר אירעה כשבעים שנה קודם לכן, החלו בשנת 1835 לצאת משלחות ראשונות של חלוצים אפריקאנרים לתור את הארץ. מסעם שלהם ושל ממשיכיהם, יכונה לימים הטרק הגדול.
משפחתו של קרוגר החליטה להצטרף לטרק הגדול, על רקע ההתלהבות הרבה אשר אחזה בציבור האפריקאנרי באותם הימים. כאשר מאות רבות נוקטים בדרך דומה, עזבה המשפחה את ביתה בקולסברג, ויצאה למסע מזרחה. באותו הזמן היה פול קרוגר בן 10 בלבד. כעבור ימים לא רבים, חצתה המשפחה את נהר האורנג', יצאה מתחומי המושבה והקימה חווה באזור סמוך, בעמק נהר הקאלדון. בחודשים הבאים משפחת קרוגר השתקעה במקום.
בראשית שנת 1836, במסגרת הטרק הגדול, יצאה ממושבת הכף משלחת מהגרים בראשות המנהיג האפריקאנרי הנדריק פוטכיטר. המשלחת הייתה הגדולה ביותר מאלו אשר יצאו ממושבת הכף עד אז, ולצד מאות חברים היא כללה גם שפע של סוסים וחיות מרעה אשר יוכלו להוות בסיס כלכלי ראשוני ליישוב החדש. יעדו של פוטכיטר היה להגיע אל חבל זאוטפאנסברג שלגדתו הדרומית של לנהר הלימפופו, שם התכוון להתאחד עם מלשחת חלוצים אפריקאנרית אחרת, אשר הגיעה לאזור מספר חודשים קודם לכן. פוטכיטר עצר עם חברי המשלחת שלו למנוחה בקרבת החווה של משפחת קרוגר בעמק נהר הקאלדון. המשפחה, אשר התרשמה מכוונותיו של פוטכיטר להקים רפובליקה עצמאית בזאוטפאנסברג, החליטה להצטרף אל המשלחת. את החודשים הבאים העבירה משפחת קרוגר בנדודים ממושכים צפונה. תוך כדי המסע, אב המשפחה הקפיד להמשיך להעניק חינוך לילדיו בכלל ולפול קרוגר בפרט. כך למשל דרש מהם להצליח לכתוב מדי יום פסוקים מקראיים מתוך זכרונם. בנוסף, מדי פעם כאשר המשלחת עצרה למנוחה, ילדי המשלחת התאספו ללמידה סביב אחד מחבריה המבוגרים.
מסעם של משפחת קרוגר כחלק מהמשלחת של פוטכיטר, היה מועד להתקפות חוזרות ונשנות מצד האוכלוסייה הילידית, אשר חשקה בבזיזת רכוש המשלחת. עד ליוני 1836, מספר חודשים לאחר יציאתם מעמק הקאלדון, הגיעו משפחת קרוגר והמשלחת אל זאוטפאנסברג, שם התאחדו עם משלחות אפריקאנריות אחרות אשר הגיעו למקום מספר שבועות קודם לכן. המהגרים הקימו מחנה והחלו בחיי שגרה ומגורים במקום. עם זאת, השהייה בזאוטפנסברג הולידה בעיות שונות. עד מהרה רבים מאנשי המשלחת הוכו במלריה ובמחלות שהביא איתו זבוב הצה צה השורץ באזור. הם נתקלו במחסור קשה במזון, והתקשו לתחזק את הכמויות הגדולות של חיות המרעה שהיו ברשותם. לאחר המתנה ארוכה של מספר חודשים, החליט מנהיג המשלחת פוטכיטר לעזוב את המקום ולשוב דרומה.
עד לשלהי שנת 1836, חצתה כבר משלחתו של פוטכיטר ועמה משפחת קרוגר את נהר הואל, ובכך הם למעשה שבו אל האזורים שהם היום המדינה החופשית, בהם שהו רק כמה חודשים קודם לכן. עם הגיעם למקום, פגשו חברי המשלחת קבוצות קטנות של אפריקאנרים אשר דיווחו על ההתקפות שספגו מצד שבט מקומי בשם הנדבלה – חוויות דומות אשר חוותה המשלחת בעצמה מספר חודשים קודם לכן בעת מעברם צפונה במקום. עקב כך החליט פוטכיטר לארגן צבא מקומי ולהוציא לפועל מספר קרבות שישברו את התנגדות הנדבלה. הקרב הראשון היה קרב וגופ (Vegkop), אשר אירע באוקטובר 1836, בסמוך לגדות נהר הואל. בתחילה התקשו כוחותיו המשלחת להשיג הכרעה מול הכוחות הגדולים שעמדו בפניהם, אך תוך זמן קצר הגיעו לעזרתם קבוצות ממשלחות טרק אחרות שבדיוק עזבו את מושבת הכף - משלחות בהנהגת חירט מאריץ ופיט רטיף. הקרב הסתיים לבסוף בניצחון אפריקאנרי. במהלך סערת הקרב, בעוד אחיו הגדולים של קרוגר ואביו לקחו חלק פעיל בלחימה, קרוגר עצמו ואחיו הקטנים סייע במשימות לוגיסטיות שונות כמו העברת תחמושת. בערוב ימיו יכתוב קרוגר על ההשפעה הגדולה של הקרב על חייו אשר במהלכו הוא היה בן 11 בלבד.
ההתיישבות בחבל נטאל.
לאחר שוך קרב וגופ, במהלך שנת 1837 עזבה משפחת קרוגר את המשלחת של פוטכיטר והחלה לנוע מזרחה אל עבר חבל נטאל. הסברה הייתה שהאזור הוא האידיאלי ביותר להקמת רפובליקה אפריקאנרית עצמאית (כפי שלימים אכן יהיה, עם הקמת רפובליקת נטאליה כעבור שלוש שנים). משפחת קרוגר הגיע לנטאל בעקבות משלחת אפריקאנרית בראשות פיט רטיף, אשר התיישבה במקום באותה התקופה. ההתיישבות האפריקאנרית בחבל נטאל הייתה תולדה של משא ומתן בין המהגרים לבין מלך הזולו דינגאנה (אחיו למחצה של שאקה אשר מת זה מכבר), אשר הסכים להתיישבות אפריקאנרית בשטחי ממלכתו בהתאם למגבלות מסוימות. משפחתו של קרוגר השתקעה בנטאל ובאותן השנים היה פול קרוגר כבר בן 12. בנטאל פגש קרוגר במיסיונר אמריקני בשם דניאל לינדלי, אשר העניק לקרוגר השכלה דתית נוספת על זו שהייתה לו, ומה שהוא יגדיר לימים בתור "התרגשות רוחנית".
בחודשים ינואר ופברואר 1838 המתיחות בין הזולו לאפריקאנרים גברה, והסתיימה לבסוף בשורה של אירועים עקובים מדם. במה שיכונה לימים טבח משלחת רטיף, טבחו אנשי הזולו בכמאה חברי קבוצה אפריקאנרית בראשות מנהיגם רטיף אשר באה אל ארמונו של דינגאנה מלך הזולו במטרה להיוועד עמו. בין ההרוגים היה גם פיט רטיף עצמו. מייד לאחר הטבח, הורה דינגאנה להוציא להורג גם את כל האפריקאנרים שהתיישבו בעצת רטיף בתחומי ממלכתו, וכן להחרים את רכושם. 534 אנשים נהרגו, לרבות 185 ילדים ו-56 נשים.
כשלצידם כמה מאות בודדות של אפריקאנרים בלבד, שרדה משפחת קרוגר את הטבח. פול קרוגר תיאר לימים את מראות הטבח כאשר כתב כי בתום הטבח היה אפשר להבחין "בילדים המשופדים על שדי אמותיהם באמצעות חניתות, וילדים שמוחם היה מנופץ על גלגלים של קרון". לאחר הטבח נקמו האפריקאנרים בזולו, ובסופו של קרב נהר הדם (Bloedrivier) אשר פרץ בין הצדדים הניצים בדצמבר 1838, מאות בודדות של לוחמים אפריקאנרים נחושים ומצוידים בנשק חם הביסו בצורה מכרעת כוח זולו עצום בגודלו של כעשרים אלף לוחמים מצוידים בחניתות ומסודרים במערכי אימפי. באופן לא מפתיע, ראו האפריקאנרים את ניצחונם בקרב כאות מבשר מהאל אל נכונות צעדיהם. הניצחון על הזולו, אשר הידיעות אודותיו התפשטו ברוב שטחי דרום אפריקה של ימינו, הביא לביסוס תדמיתם של האפריקאנרים כעם נחוש ובלתי מנוצח, אשר מהווה את הכוח הדומיננטי היחיד בטריטוריות שמחוץ לתחומי המושבה הבריטית. קרוגר תיאר את האירועים בהתלהבות רבה, וקבע כי למרות הטבח המזעזע שנערך באפריקאנרים בחבל נטאל, "אלוהים שמע את תפילתנו... אצנו בעקבותיהם וירינו בהם במנוסתם, עד שהסבנו להם יותר הרוגים מאשר מספר ההרוגים מקרבנו שספגנו בהתקפה שלהם".
ההתבססות בטרנסוואל.
עוד קודם קרב נהר הדם, עזב קרוגר את חבל נטאל ונע יחד עם משפחתו מערבה אל שטחי המדינה החופשית של ימינו. לאחר שמשפחת קרוגר הייתה עדה לקרבות של אפריקאנרים באזורים אלו כנגד שבטים ילידיים שונים, התיישבה המשפחה בקרבת רסטנבורג של ימינו, כחמישים קילומטרים מצפון לנהר הואל. הגעת המשפחה לאזור סימנה את חזרתה לשגרת חיים מסודרת לראשונה מזה שנים. בני המשפחה בנו את ביתם והחלו לעבד את הקרקע באזור. בשנת 1841, בהגיעו של פול קרוגר לגיל 16, עזב קרוגר את משפחתו כארבעים קילומטר מזרחה ושם הקים את ביתו בכפר חדש בשם וואטקלוף, אשר קם באזור שהוא היום צפון העיר פרטוריה. בוואטקלוף פגש קרוגר הצעיר את מריה פלרסיס, בתו של מנהיג אפריקארני מקומי, ומייד החליט להתחתן עמה. בנישואיהם היה קרוגר בן 17 ומריה הייתה בת 14 בלבד. טקס החתונה נערך בשנת 1842 בפוצ'פסטרום, אשר היה היישוב האפריקאנרי הגדול ביותר באזור באותן השנים.