พล.ต.อ.ประชา พรหมนอก เข้าสู่แวดวงการเมืองครั้งแรกเมื่อได้รับแต่งตั้งให้เป็นสมาชิกวุฒิสภาในปี พ.ศ. 2540 ภายหลังเกษียณราชการแล้ว ต่อมาได้เป็นสมาชิกสภาผู้แทนราษฎร แบบบัญชีรายชื่อ พรรคชาติพัฒนา[7] และได้ดำรงตำแหน่งรัฐมนตรีว่าการกระทรวงแรงงานและสวัสดิการสังคม ในรัฐบาล นายชวน หลีกภัย ต่อมาได้ย้ายมาเป็นสมาชิกพรรคเพื่อแผ่นดิน และได้รับเลือกให้เป็นหัวหน้าพรรคแทนที่นายสุวิทย์ คุณกิตติ ที่ประกาศลาออกไป และได้รับแต่งตั้งให้เป็นรัฐมนตรีว่าการกระทรวงอุตสาหกรรมในรัฐบาลนายสมชาย วงศ์สวัสดิ์[8]

ภายหลังรัฐบาลนายสมชายต้องพ้นวาระไปจากคดียุบพรรคพลังประชาชน ทำให้ตำแหน่งนายกรัฐมนตรีต้องว่างลง พล.ต.อ.ประชาได้รับการสนับสนุนจากนายเสนาะ เทียนทอง และพรรคเพื่อไทยให้ดำรงตำแหน่งนายกรัฐมนตรีเป็นคนต่อไป ในวันที่เลือกนายกรัฐมนตรีที่รัฐสภา เสียงที่เลือก พล.ต.อ.ประชา แพ้นายอภิสิทธิ์ เวชชาชีวะ ด้วยคะแนน 198 ต่อ 235 เสียง ซึ่ง พล.ต.อ.ประชาได้โหวตให้แก่ตัวเองด้วย

ต่อมา พล.ต.อ.ประชา ได้ลาออกจากการเป็นสมาชิกพรรคเพื่อแผ่นดิน ในเดือนเมษายน พ.ศ. 2554[9] และเข้าเป็นสมาชิกพรรคเพื่อไทย[10] และได้รับโปรดเกล้าฯ แต่งตั้งเป็นรัฐมนตรีว่าการกระทรวงยุติธรรม ในรัฐบาลของนางสาวยิ่งลักษณ์ ชินวัตร เมื่อวันที่ 9 สิงหาคม พ.ศ. 2554[11] และจากการสำรวจความพึงพอใจของประชาชน โดยสำนักเอแบคโพล เมื่อเดือนพฤษภาคม พ.ศ. 2555 เขาเป็นรัฐมนตรีที่ประชาชนพึงพอใจ เป็นลำดับที่ 5[12] จนกระทั่งในเดือนมิถุนายน พ.ศ. 2556 เขาได้รับแต่งตั้งเป็นรองนายกรัฐมนตรี[13]

ในเดือนพฤศจิกายน พ.ศ. 2556 พล.ต.อ.ประชา ได้รับแต่งตั้งให้ทำหน้าที่ผู้อำนวยการศูนย์อำนวยการรักษาความสงบเรียบร้อย (ศอ.รส.) ในช่วงที่มีการชุมนุมทางการเมืองของกลุ่มต่อต้านรัฐบาล ต่อมาได้มีการแต่งตั้ง ดร.สุรพงศ์ โตวิจักษณ์ชัยกุล เข้ามาทำหน้าที่แทน[14]

ในการเลือกตั้งสมาชิกสภาผู้แทนราษฎรไทยเป็นการทั่วไป พ.ศ. 2557 เขาได้สมัครรับเลือกตั้งในระบบบัญชีรายชื่อ สังกัดพรรคเพื่อไทย ลำดับที่ 8[15] ซึ่งการเลือกตั้งในครั้งนั้นถูกศาลรัฐธรรมนูญตัดสินให้เป็นโมฆะ เนื่องจากไม่สามารถจัดให้มีการเลือกตั้งทั้งราชอาณาจักรในวันเดียวกันได้ ซึ่งขัดรัฐธรรมนูญ[16]

วันที่ 7 พฤษภาคม พ.ศ. 2557 พล.ต.อ.ประชา ถูกศาลรัฐธรรมนูญตัดสินให้พ้นจากความเป็นรัฐมนตรี เนื่องจากมีส่วนเกี่ยวข้องในการโยกย้ายนายถวิล เปลี่ยนศรีจากตำแหน่งเลขาธิการ สภาความมั่นคงแห่งชาติ โดยขาดความชอบธรรม[17]