พจน์ พหลโยธิน มีบิดาชื่อว่านายกิ่ม (ต่อมาได้บรรดาศักดิ์เป็นพระยาพหลพลพยุหเสนา[4]) มหาดเล็กในรัชกาลที่ห้า มารดาชื่อว่านางจับซึ่งเป็นภรรยาคนที่ห้าของนายกิ่ม ภายหลังบิดาของพจน์ถึงแก่อนิจกรรม พจน์ก็อยู่ภายใต้การอุปการะของพี่ชายต่างมารดาที่ชื่อนพ (ต่อมาได้บรรดาศักดิ์เป็นพระยาพหลโยธินรามนิทราภักดี)

เมื่ออายุราว 8 ขวบ บิดาได้พาไปฝากกับขุนอนุกิจวัตร ครูใหญ่โรงเรียนวัดจักรวรรดิราชาวาสวรมหาวิหาร และย้ายไปศึกษาต่อที่โรงเรียนสุขุมาลลัย (ปัจจุบันคือโรงเรียนวัดพิชัยญาติ) และในปีพ.ศ. 2544 จึงเข้าศึกษาที่โรงเรียนนายร้อยทหารบก[3] ครั้นถึงปลายปี พ.ศ. 2447 พจน์ในวัยสิบหกปีได้รับทุนหลวงและออกเดินทางไปศึกษาวิชาทหารปืนใหญ่ที่จักรวรรดิเยอรมัน พจน์เข้าเรียนที่โรงเรียนเตรียมนายร้อยในเมืองพ็อทซ์ดัมเป็นเวลาหนึ่งปี และเข้าเรียนที่โรงเรียนนายร้อยปรัสเซียในกรุงเบอร์ลินอีกสองปี[5] ซึ่งที่นี่ พจน์และนักเรียนไทยหลายคนได้เป็นเพื่อนร่วมชั้นกับแฮร์มัน เกอริง กับฮิเดกิ โทโจ[6] เมื่อจบการศึกษาในปีพ.ศ. 2450 พจน์เข้ารับราชการทหารในกรมทหารปืนใหญ่ที่ 4 ของกองทัพปรัสเซีย