เพาล์ ฟ็อน ฮินเดินบวร์ค เกิดเมื่อวันที่ 2 ตุลาคม ค.ศ. 1847 ในเมืองโพเซิน ราชอาณาจักรปรัสเซีย จักรวรรดิเยอรมัน[3] (ปัจจุบันตั้งอยู่ในโปแลนด์) เป็นบุตรคนโตขุนนางปรัสเซีย ฮันส์ โรแบร์ท ลูทวิช ฟ็อน เบ็นเน็คเคินดอร์ฟ อุนท์ ฟ็อน ฮินเดินบวร์ค (Hans Robert Ludwig von Beneckendorff und von Hindenburg) กับนางลูอีเซอ ชวิคคาร์ท (Luise Schwickart) ตระกูลฮินเดินบวร์คเป็นทายาทสืบสายตรงของมาร์ติน ลูเทอร์ เพาล์มีน้องสามคน นามว่า อ็อทโท (เกิด 1849), อีดา (เกิด 1851) และแบร์นฮาร์ท (เกิด 1859)

เพาล์มีความภาคภูมิใจในตระกูลของตนเองมาก ตระกูลของเขาสามารถสืบประวัติย้อนไปได้ถึงปีค.ศ. 1289[4] นามสกุลคู่ "เบ็นเน็คเคินดอร์ฟ-ฮินเดินบวร์ค" เริ่มถูกใช้ในปีค.ศ. 1789 เพื่อแสดงความสืบตระกูลในเอกสารราชการ แต่ชีวิตประจำวันพวกเขาใช้เพียงสกุลเบ็นเน็คเคินดอร์ฟเท่านั้น