เขตพระโขนงเดิมมีฐานะเป็น อำเภอพระโขนง เป็นเขตการปกครองของเมืองนครเขื่อนขันธ์ ปรากฏชื่อเท่าที่สืบค้นได้ตั้งแต่ พ.ศ. 2445[2] (เมืองนครเขื่อนขันธ์เปลี่ยนชื่อเป็นเมืองพระประแดงใน พ.ศ. 2457 และเปลี่ยนแปลงฐานะเป็นจังหวัดพระประแดงใน พ.ศ. 2459)[2] ในสมัยแรกตั้งที่ว่าการอำเภออยู่ที่สามแยกวัดมหาบุศย์ (บริเวณที่คลองตันบรรจบคลองพระโขนง) แบ่งท้องที่การปกครองออกเป็น 12 ตำบล ได้แก่ ตำบลคลองเตย ตำบลคลองตัน ตำบลพระโขนง ตำบลสวนหลวง ตำบลศีรษะป่า (หัวป่า) ตำบลคลองประเวศ ตำบลทุ่งดอกไม้ ตำบลหนองบอน ตำบลบางจาก ตำบลบางนา ตำบลสำโรง และตำบลบางแก้ว[3] จากนั้นจึงย้ายที่ว่าการอำเภอมาตั้งที่วัดสะพาน ริมทางรถไฟสายปากน้ำ เมื่อ พ.ศ. 2459[3]

จนกระทั่งใน พ.ศ. 2470 ทางราชการได้โอนอำเภอพระโขนงมาขึ้นกับจังหวัดพระนครเพื่อความสะดวกในการปกครอง[4] ก่อนที่จังหวัดพระประแดงจะถูกยุบและแยกพื้นที่ไปรวมกับจังหวัดธนบุรีและจังหวัดสมุทรปราการ 5 ปี[5] และเนื่องจากท้องที่อำเภอพระโขนงเริ่มมีสภาพเป็นชุมชน ย่านการค้า อุตสาหกรรม และที่พักอาศัยหนาแน่น ใน พ.ศ. 2479 ทางราชการจึงได้ตั้งเทศบาลนครกรุงเทพโดยโอนพื้นที่บางส่วนของตำบลคลองเตยเข้าไปในท้องที่[6] และได้ขยายเขตเทศบาลออกไปครอบคลุมตำบลอื่น ๆ เกือบทั้งหมดในอำเภอภายใน พ.ศ. 2507[7] ในช่วงนี้ที่ว่าการอำเภอพระโขนงได้ย้ายจากวัดสะพานมาตั้งอยู่ริมถนนสุขุมวิท (ที่ตั้งสำนักงานเขตปัจจุบัน) แล้วตั้งแต่ปี พ.ศ. 2495[3]

ใน พ.ศ. 2514 จังหวัดพระนครถูกรวมเข้ากับจังหวัดธนบุรี เปลี่ยนฐานะเป็นนครหลวงกรุงเทพธนบุรี[8] และใน พ.ศ. 2515 จึงเปลี่ยนแปลงฐานะเป็นกรุงเทพมหานคร[9] ซึ่งได้ยกเลิกการปกครองท้องถิ่นแบบเทศบาลและสุขาภิบาล รวมทั้งเปลี่ยนการเรียกหน่วยการปกครองใหม่จากอำเภอและตำบลเป็นเขตและแขวงด้วย อำเภอพระโขนงจึงได้รับการเปลี่ยนแปลงฐานะเป็น เขตพระโขนง แบ่งออกเป็น 9 แขวงตามจำนวนตำบลที่มีอยู่เดิมก่อนการปรับปรุงรูปแบบการบริหารเมืองหลวง

ภายหลังเขตพระโขนงมีความเจริญและมีประชากรหนาแน่นขึ้น ใน พ.ศ. 2532 กรุงเทพมหานครได้จัดตั้งสำนักงานเขตสาขาของเขตพระโขนงขึ้น 3 แห่งขึ้นดูแลท้องที่ต่าง ๆ[10][11][12] เพื่อให้การปกครองและการอำนวยความสะดวกแก่ประชาชนเป็นไปอย่างมีประสิทธิภาพ และในปีเดียวกัน กระทรวงมหาดไทยก็ได้ยกฐานะท้องที่ของสำนักงานเขตพระโขนง สาขา 1 และสำนักงานเขตพระโขนง สาขา 2 เป็นเขตคลองเตยและเขตประเวศตามลำดับ[13] (ส่วนท้องที่ของสำนักงานเขตพระโขนง สาขา 3 โอนไปเป็นของเขตประเวศจนกระทั่งใน พ.ศ. 2537 จึงแยกออกไปเป็นเขตสวนหลวง)[14]

เมื่อ พ.ศ. 2541 มีการเปลี่ยนแปลงพื้นที่เขตพระโขนงอีกครั้ง โดยแขวงบางนาและบางส่วนของแขวงบางจากได้รับการยกฐานะเป็นเขตบางนา[15] ท้องที่เขตพระโขนงจึงเหลือแขวงบางจากอยู่เพียงแขวงเดียวจนกระทั่ง พ.ศ. 2560 จึงมีการแบ่งแขวงการปกครองในเขตพระโขนงออกเป็นสองแขวง