เรือนจำปูดูถูกสร้างขึ้นบนพื้นที่ซึ่งเคยเป็นสุสานชาวจีนมาก่อน สถานที่แห่งนี้ถูกเลือกเพราะในขณะนั้นปูดูเป็นป่าทึบ มีเสือมาลายันเดินเตร่ไปมาเป็นครั้งคราว และยังเป็นเพราะในขณะนั้นอยู่ใกล้กับย่านธุรกิจใจกลางเมืองของกัวลาลัมเปอร์ (ห่างจากอาคารสุลต่านอับดุลซามัด ประมาณ 1 ไมล์ ) แต่ก็ยังค่อนข้างเงียบสงบชาร์ลส์ เอ็ดวิน สปูนเนอร์หัวหน้ากรมโยธาธิการของรัฐเซลังง อ ร์ เป็นสถาปนิกและผู้จัดการโครงการ^{[ 4 ]}เรือนจำแห่งนี้สร้างขึ้นด้วยงบประมาณ 138,000 ดอลลาร์สเตรตส์

การก่อสร้างเริ่มขึ้นในปี พ.ศ. 2434 โดยมีนักโทษทำหน้าที่เป็นแรงงาน สุสานถูกขุดและซากศพจากหลุมศพ 500 หลุมถูกย้ายไปยังสุสานอื่น นักโทษถูกย้ายไปยังเรือนจำที่สร้างไม่เสร็จเป็นระยะๆ ตลอดช่วงการก่อสร้างตั้งแต่ปี พ.ศ. 2435 ถึง พ.ศ. 2438 ^{[ 5 ] [ 6 ]}ในขณะที่อาคารหลักของเรือนจำสร้างเสร็จเพียงครึ่งเดียว นักโทษประมาณ 500 คนจากเรือนจำขนาดเล็กอื่นๆ ทั่วกรุงกัวลาลัมเปอร์ถูกย้ายไปยังเรือนจำปูดูในเดือนพฤษภาคม พ.ศ. 2438 ผู้ว่าการเรือนจำปูดูคนแรกคือ พันโทหญิง เจ.บี. เอลเลน

ตั้งแต่ปี พ.ศ. 2436 ถึง พ.ศ. 2438 เกิดการระบาดของอหิวาตกโรคและโรคบิดในเรือนจำ ทำให้มีนักโทษเสียชีวิตจำนวนมาก การระบาดถึงจุดสูงสุดในเดือนสิงหาคม พ.ศ. 2438 ซึ่งตรงกับช่วงที่มีอากาศแห้งผิดปกติ ส่งผลให้มีผู้ป่วยที่ได้รับการบันทึกไว้ 126 ราย รวมทั้งผู้เสียชีวิต 68 รายในเดือนนั้นเพียงเดือนเดียว^{[ 7 ] [ 6 ]}

สาเหตุของการระบาดของโรคถูกกล่าวโทษว่าเป็นเพราะระบบน้ำประปาของเรือนจำ ซึ่งมาจากบ่อน้ำที่สร้างอยู่บนพื้นที่ฝังศพเก่า น้ำในบ่อน้ำยังปนเปื้อนด้วยน้ำเสียจากสวนผักในหมู่บ้านใกล้เคียง การระบาดของโรคถูกควบคุมได้ในปลายเดือนสิงหาคม ค.ศ. 1895 เมื่อได้น้ำสะอาดจากอ่างเก็บน้ำในอำเภออัมปังมาใช้

การระบาดของโรคเหน็บชายังสร้างปัญหาให้กับเรือนจำในช่วงทศวรรษแรกของการดำเนินงาน และตามมาด้วย การระบาด ของโรคมาลาเรียในปี พ.ศ. 2451 ^{[ 8 ]}

ในปี พ.ศ. 2454 ริชาร์ด อัลเฟรด เออร์เนสต์ คลาร์ก อดีตทหารจากกองพันที่สามของกรมทหารมิดเดิลเซ็กซ์เป็นหนึ่งในผู้คุมชาวยุโรปที่เรือนจำปูดู^{[ 9 ]}

ในช่วงต้นประวัติศาสตร์ เรือนจำปูดูเป็นเรือนจำแห่งเดียวในรัฐเซลังงอร์ที่ใช้คุมขังนักโทษชายและหญิงที่รับโทษจำคุกระยะสั้น นอกจากนี้เรือนจำยังพึ่งพาตนเองได้เนื่องจากมีสวนผักที่สามารถผลิตอาหารเพียงพอสำหรับนักโทษได้ตลอดทั้งปี^{[ 10 ]}

ต่อมาเรือนจำแห่งนี้ได้คุมขังนักโทษที่ก่ออาชญากรรมร้ายแรงมากขึ้น รวมถึงผู้ค้ายาเสพติดและฆาตกรโทษประหารชีวิตด้วยการแขวนคอถูกกระทำในห้องประหารในบล็อก D ซึ่งเป็นที่คุมขังนักโทษประหาร นอกจากนี้ยังมีการลงโทษทางร่างกาย ด้วยการเฆี่ยนด้วยหวายในลานที่กำหนดไว้ภายในบริเวณเรือนจำด้วย

ในช่วงสงครามโลกครั้งที่สองเรือนจำแห่งนี้ถูกใช้โดยชาวญี่ปุ่นเป็นค่ายเชลยศึกชั่วคราวตั้งแต่เดือนมกราคมถึงตุลาคม พ.ศ. 2485 หลังจากนั้นเชลยศึกส่วนใหญ่ถูกย้ายไปยังเรือนจำชางงีในสิงคโปร์ มีเชลยศึกมากกว่า 1,000 คนถูกคุมขังอยู่ที่นั่นในช่วงกลางปี ​​พ.ศ. 2485 ^{[ 2 ]}

ในปี 1986 กลุ่มนักโทษนำโดยจิมมี่ ชัว ชัป เซงได้จับเจ้าหน้าที่เรือนจำสองคนเป็นตัวประกันนานถึงหกวัน เหตุการณ์คลี่คลายลงเมื่อตำรวจมาเลเซียบุกเข้าไปในเรือนจำ ช่วยเหลือตัวประกันได้สำเร็จ และปราบปรามกลุ่มนักโทษได้โดยไม่มีผู้เสียชีวิต ชัวถูกแขวนคอในข้อหาอื่นที่เขาถูกคุมขังในเรือนจำปูดู ส่วนที่เหลือถูกจำคุกในข้อหาคุมขังโดยมิชอบและลักพาตัว

ในช่วงทศวรรษ 1990 มีข้อกังวลเกิดขึ้นเกี่ยวกับความเหมาะสมของที่ตั้งเรือนจำบนที่ดินทำเลทองในกรุงกัวลาลัมเปอร์ ความปลอดภัยเป็นประเด็นสำคัญเนื่องจากเรือนจำอยู่ใกล้กับแหล่งพัฒนาเชิงพาณิชย์ที่เติบโตอย่างรวดเร็ว เช่นบูกิตบินตังนอกจากนี้ โครงสร้างและสิ่งอำนวยความสะดวกของเรือนจำก็ล้าสมัยไปแล้ว

ในปี 1996 หลังจากเปิดดำเนินการเป็นเรือนจำมา 101 ปี เรือนจำปูดูถูกปิดอย่างเป็นทางการ และนักโทษถูกย้ายไปยังเรือนจำซูไงบูโลห์และเรือนจำกาจัง เรือนจำปูดูยังคงถูกใช้เป็นสถานที่ควบคุมตัวนักโทษระหว่างรอการพิจารณาคดีจนถึงปี 2009 นอกจากนี้ยังเคยเปิดให้ประชาชนเข้าชมในฐานะพิพิธภัณฑ์ในช่วงสั้นๆ ในปี 1997 ในปี 2007 ผู้สนับสนุน กลุ่มเคลื่อนไหว เพื่อสิทธิของชาวฮินดู (Hindu Rights Action Force หรือ HINDRAF) จำนวน 8 คน ถูกจับกุมและคุมขังในเรือนจำปูดูหลังจากการชุมนุมของ HINDRAF ในปี 2007ต่อมาพวกเขาได้รับการปล่อยตัวเนื่องจากขาดหลักฐาน

ในเดือนมิถุนายน พ.ศ. 2552 รัฐบาลมาเลเซียตัดสินใจรื้อถอนเรือนจำเป็นระยะ เมื่อฟง กุยลุน ( DAP ) สมาชิกสภาผู้แทนราษฎรเขตบูกิตบินตังถามว่าทำไมอาคารนี้จึงไม่ถูกเก็บรักษาไว้เป็นส่วนหนึ่งของมรดกของมาเลเซีย รองรัฐมนตรีว่าการกระทรวงการคลังอาวัง อาเดก ฮุสเซน ( UMNO - BN ) ตอบว่า "ในความคิดของเรา มันไม่ใช่สิ่งที่น่าภาคภูมิใจ" ^{[ 3 ]}ห้องประหารชีวิตพร้อมกับโรงพยาบาลเรือนจำเป็นสิ่งก่อสร้างแรกที่ถูกรื้อถอนในเดือนตุลาคมของปีนั้น^{[ 11 ]}

ในเดือนมิถุนายน พ.ศ. 2553 กำแพงด้านตะวันออกของเรือนจำปูดูถูกรื้อถอนเพื่อเปิดทางให้กับโครงการขยายถนน^{[ 2 ]}ภายในเดือนธันวาคม พ.ศ. 2555 อาคารทั้งหมดภายในเรือนจำปูดูถูกรื้อถอนจนหมด รัฐบาลตกลงที่จะคงส่วนหนึ่งของกำแพงด้านนอกและประตูหลักไว้หลังจากได้รับการร้องขอจากนักอนุรักษ์และประชาชนทั่วไป ส่วนที่เหลือเหล่านี้ได้ถูกรวมเข้ากับสวนน้ำพุซึ่งเป็นส่วนหนึ่งของห้างสรรพสินค้าMitsui Lalaport Mallซึ่งปัจจุบันตั้งอยู่บนพื้นที่ของเรือนจำ

พื้นที่ดังกล่าวได้รับการพัฒนาใหม่โดย BBCC Development Sdn Bhd ซึ่งเป็นการร่วมทุนระหว่างEcoWorld , UDAและEPF Boardให้เป็นBukit Bintang City Centre (BBCC) ^{[ 12 ] [ 13 ]}ในปี 2022 BBCC ได้เปิดอย่างเป็นทางการ เหตุผลหลักที่อังกฤษปิดเรือนจำปูดูคือเรือนจำไม่สามารถรองรับนักโทษทั้งหมดได้อีกต่อไป นักโทษทั้งหมดถูกย้ายไปยังเพนจารา กาจังเป็นกลุ่มๆ