ร้อยตำรวจเอก เฉลิม อยู่บำรุง ปรากฏบทบาททางการเมืองครั้งแรกในฐานะผู้ร่วมการพยายามก่อรัฐประหารรัฐบาลพลเอก เปรม ติณสูลานนท์ ในเดือนเมษายน พ.ศ. 2524 และหลังการทำรัฐประหารไม่สำเร็จ จึงตกเป็นผู้ต้องหามีคำสั่งย้ายเข้ากรมตำรวจในวันที่ 5 เมษายน พ.ศ. 2524 และพลตำรวจเอกมนต์ชัย พันธุ์คงชื่นอธิบดีกรมตำรวจในขณะนั้น ได้ลงนามในคำสั่งที่ 500/2524 ไล่ออกจากราชการตำรวจในวันที่ 7 เมษายน พ.ศ. 2524[13]และตั้งคณะกรรมการสอบสวนวินัยร้ายแรง ต่อมาจึงได้รับการนิรโทษกรรม[ต้องการอ้างอิง]

ร้อยตำรวจเอก เฉลิม เริ่มต้นชีวิตทางการเมืองด้วยการเป็นสมาชิกสภาผู้แทนราษฎรกรุงเทพมหานคร ในปี 2526 ในฐานะสมาชิกสภาผู้แทนราษฎรสังกัดพรรคประชาธิปัตย์ ต่อมาในปี พ.ศ. 2529 ได้ก่อตั้ง พรรคมวลชน และดำรงตำแหน่งเป็นหัวหน้าพรรค โดยมีฐานเสียงสำคัญในพื้นที่กรุงเทพมหานครฝั่งธนบุรี โดยเฉพาะเขตภาษีเจริญและเขตบางบอน

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

ภายหลังการรัฐประหารดังกล่าว ร้อยตำรวจเอก เฉลิม อยู่บำรุง เป็นหนึ่งในนักการเมืองที่ถูกกล่าวหาว่าร่ำรวยผิดปกติ และถูกยึดทรัพย์จำนวน 32 ล้านบาท [16] และต้องขอลี้ภัยการเมืองไปต่างประเทศ โดยเดินทางไปพำนักอยู่ที่ประเทศสวีเดนและประเทศเดนมาร์ก

ต่อมาเมื่อสถานการณ์ทางการเมืองคลี่คลาย ร้อยตำรวจเอก เฉลิม อยู่บำรุง ได้กลับเข้าประเทศไทย และได้ดำรงตำแหน่งรัฐมนตรีว่าการกระทรวงยุติธรรมในรัฐบาลของนายบรรหาร ศิลปอาชา และรัฐมนตรีช่วยว่าการกระทรวงมหาดไทย ในรัฐบาลพลเอกชวลิต ยงใจยุทธ[17] ต่อมา ในปี พ.ศ. 2540 ตัดสินใจยุบพรรคมวลชนรวมเข้ากับ พรรคความหวังใหม่ ของ พลเอก ชวลิต ยงใจยุทธ นายกรัฐมนตรีในขณะนั้น