สโมสรเอ็กซ์เพรสเข้าร่วมลีกฟุตบอลคัมปาลาและเขต (KDFL) และในปี 1964 ก็กลายเป็นทีมชั้นนำในการแข่งขัน โดยคว้าแชมป์ดิวิชั่นหนึ่งได้สำเร็จ โดยอาลี คิโตนซา ผู้ทำประตูสูงสุดของสโมสร ยิงได้ 54 ประตูจากการลงเล่น 18 นัด ในฤดูกาล1968–69สโมสรได้เข้าร่วมการแข่งขันในฤดูกาลแรกของลีกแห่งชาติดิวิชั่นหนึ่ง และจบอันดับที่สี่

เรดอีเกิลส์คว้าแชมป์ลีกแห่งชาติยูกันดาเป็นครั้งแรกในปี 1974และทำซ้ำความสำเร็จนั้นได้อีกครั้งในฤดูกาลถัดมาในปี 1975ใน ฤดูกาล 1977 เอ็กซ์เพรสเอาชนะ ซิมบ้าเอฟซีทีมของกองทัพบกไปได้ 2-0 ในการแข่งขันลีกที่สำคัญ และต่อมาถูกแบนเนื่องจากถูกกล่าวหาว่ามีส่วนเกี่ยวข้องกับกิจกรรมต่อต้านรัฐบาล โดยผู้ว่าราชการจังหวัดภาคกลาง พันเอก อับดัลลาห์ นาซูร์ ซึ่งไม่พอใจกับการแพ้ของทีม ในปี 1979 การแบนถูกยกเลิกหลังจากระบอบการปกครองของอิดิ อามินสิ้นสุดลง และเอ็กซ์เพรสกลับมาสู่ลีกแห่งชาติในฤดูกาล1980 ^{[ 8 ]}

ช่วงเวลาสั้นๆ ที่เรดอีเกิลส์หยุดพักจากการแข่งขันฟุตบอลเนชั่นแนลลีกส่งผลกระทบในระยะยาว เนื่องจากทำให้เกิดการพัฒนาทีมเยาวชนนาคิบูโบบอยส์ เจ้าหน้าที่ของเอ็กซ์เพรสทุกคนหันไปให้ความสนใจนาคิบูโบบอยส์และวางแผนให้ทีมใหม่นี้กลายเป็นทีมฟุตบอลที่แข็งแกร่งในยูกันดา นาคิบูโบบอยส์เปลี่ยนชื่อเป็นนาคิบูโบวิลลา และต่อมาเปลี่ยนชื่อเป็นสปอร์ตส์คลับวิลลา^{[ 5 ] [ 6 ]}

จนกระทั่ง ฤดูกาล 1993เอ็กซ์เพรสจึงคว้าแชมป์ซูเปอร์ลีกได้สำเร็จ และหลังจากนั้นก็เป็นช่วงเวลาที่ประสบความสำเร็จที่สุดในประวัติศาสตร์ของสโมสร โดยคว้าแชมป์ลีกได้อีกในปี 1995และ1996แต่แล้วเรื่องอื้อฉาวเกี่ยวกับการล็อกผลการแข่งขันที่เกี่ยวข้องกับวิลลา คู่ปรับตลอดกาลของเอ็กซ์เพรส ก็ได้ขัดจังหวะช่วงเวลาที่ประสบความสำเร็จนี้ เรื่องอื้อฉาวถึงจุดสูงสุดในฤดูกาล 2002–03และในตอนท้ายของฤดูกาลนี้ ทำให้ฟุตบอลยูกันดาเสื่อมเสียชื่อเสียงอย่างมาก โดยวิลลาทำประตูใส่ Akol FC ถึง 22 ประตู และคว้าแชมป์ลีกด้วยผลต่างประตูได้เสียเหนือกว่าเอ็กซ์เพรส^{[ 9 ]}

ในช่วงสิบปีที่ผ่านมา ผลงานในลีกของสโมสรลดลง แม้ว่าในฤดูกาล 2011–12เรดอีเกิลส์จะคว้าแชมป์ซูเปอร์ลีกได้อีกครั้ง โดยจบฤดูกาลด้วยคะแนนนำบุนัมวาญา เอสซี หนึ่งแต้ม ในฤดูกาลถัดมาคือ2012–13สโมสรจบฤดูกาลในอันดับที่ 11 ซึ่งเป็นอันดับต่ำที่สุดในลีกสูงสุด ในปี 2018 มีการจัดแคมเปญระดมทุนเพื่อช่วยทีมให้รอดพ้นจากการตกชั้น^{[ 7 ]}เอ็กซ์เพรสรอดพ้นจากการตกชั้นอย่างหวุดหวิดในฤดูกาล 2017–18 โดยรักษาตำแหน่งไว้ได้หลังจากเอาชนะมาซาวู ทีมบ๊วย 1–0 ในเกมสุดท้ายของฤดูกาล^{[ 10 ]}การจบฤดูกาลในอันดับที่ 13 กลายเป็นอันดับต่ำที่สุดในลีกสูงสุดของพวกเขา

ตรงกันข้ามกับผลงานในลีก เอ็กซ์เพรสเป็นสโมสรที่ประสบความสำเร็จมากที่สุดใน ฟุตบอล ถ้วยยูกันดาโดยคว้าแชมป์ได้ถึง 10 ครั้ง ในปี 1985 , 1991 , 1992 , 1994 , 1995 , 1997 , 2001 , 2002–03 , 2006และ2006–07พวกเขายังเข้าร่วมการแข่งขันฟุตบอลถ้วยระดับแอฟริกาหลายครั้ง รวมถึงการเข้าร่วมCAF Champions League 1 ครั้ง , African Cup of Champions Clubs 6 ครั้ง , CAF Confederation Cup 2 ครั้ง, CAF Cup 2 ครั้งและCAF Cup Winners' Cup 5 ครั้ง ในปี 1995ทีม "นกอินทรีแดง" เข้าถึงรอบรองชนะเลิศของ African Cup of Champions Clubs ก่อนจะตกรอบด้วยผลรวม 2–1 ให้กับสโมสรจากแอฟริกาใต้ออร์แลนโด ไพเรตส์ซึ่งเป็นแชมป์ในที่สุด นอกจากนี้ สโมสรยังเคยได้รองชนะเลิศในการ แข่งขัน CECAFA Clubs Cupซึ่งเป็นการแข่งขันระดับสโมสรในภูมิภาคแอฟริกาตะวันออกและแอฟริกากลางถึงสองครั้ง ในปี 1994 และ 1995 ความสำเร็จอีกอย่างหนึ่งคือการคว้าแชมป์ East African Hedex Super Cup ในฤดูกาล 2001–02

^{[ 12 ]}

ฤดูกาล	การแข่งขัน	กลม	คลับ	ขาที่ 1	ขาที่ 2	มวลรวม
พ.ศ. 2518	แอฟริกันคัพออฟแชมเปียนส์คลับ	รอบแรก	ฮอร์สเซด เอฟซี	1–0	0–0	1–0
		รอบที่สอง	ฆาซล์ อัล-เมฮัลลา	1–1	0–1	1–2
พ.ศ. 2519	แอฟริกันคัพออฟแชมเปียนส์คลับ	รอบแรก	ไคมาน ดูอาลา	1–0	0–1	1–1 (4–3 หน้า )
		รอบที่สอง	เอนูกู เรนเจอร์ส	0–0	2–2	2–2 ( ag. )
พ.ศ. 2529	แอฟริกัน คัพ วินเนอร์ส คัพ	รอบแรก	อัล อาห์ลี	0–2	1–0	1–2
1989	แอฟริกันคัพออฟแชมเปียนส์คลับ	รอบแรก	เอ็มบาบาเน ไฮแลนเดอร์ส เอฟซี	4–0	1–2	5–2
		รอบที่สอง	สโมสรฟุตบอลซิมบับเวเซนต์ส	1–0	0–1	1–1 (3–4 หน้า )
1992	แอฟริกัน คัพ วินเนอร์ส คัพ	รอบแรก	อัล-เมอร์เรค	0–1	1–1	1–2
พ.ศ. 2536	แอฟริกัน คัพ วินเนอร์ส คัพ	รอบแรก	อัล-เมอร์เรค	0–3	2–0	2–3
พ.ศ. 2537	แอฟริกันคัพออฟแชมเปียนส์คลับ	รอบแรก	ซามาเลก เอสซี	ถูกตัดสิทธิ์	ถูกตัดสิทธิ์	โดยไม่
พ.ศ. 2538	แอฟริกันคัพออฟแชมเปียนส์คลับ	รอบแรก	กองกำลังความมั่นคงแห่งชาติ	2–0	7–0	9–0
		รอบที่สอง	ไอเกิล เอ็นคองซัมบา	3–0	0–1	3–1
		รอบก่อนรองชนะเลิศ	ไดนาโมส์	0–1	2–1	2–2 ( ag. )
		รอบรองชนะเลิศ	ออร์แลนโด ไพเรตส์	0–1	1–1	1–2
พ.ศ. 2539	แอฟริกันคัพออฟแชมเปียนส์คลับ	รอบคัดเลือก	ซันไรส์ แฟลค ยูไนเต็ด	1–0	1–3	2–3
พ.ศ. 2540	ซีเอฟ แชมเปียนส์ลีก	รอบคัดเลือก	ชาวแอฟริกันรุ่นเยาว์	0–0	1–0	1–0
		รอบแรก	แคปส์ ยูไนเต็ด	2–5	4–2	6–7
1998	แอฟริกัน คัพ วินเนอร์ส คัพ	รอบแรก	อัล-มูราดา	0–0	1–0	1–0
		รอบที่สอง	เอสเปร็องซ์	1–0	0–2	1–2
1999	ซีเอฟ คัพ	รอบแรก	เมดลอว์ เมกบี	0–1	6–0	6–1
		รอบที่สอง	เอตัวล์ ดู ซาเฮล	2–2	0–2	2–4
2002	แอฟริกัน คัพ วินเนอร์ส คัพ	รอบแรก	ฆาซล์ อัล-เมฮัลลา	2–1	1–2	3–3 (1–4 หน้า )
2003	ซีเอฟ คัพ	รอบแรก	ควายเขียว	1–2	1–1	2–3
2004	CAF คอนเฟเดอเรชั่น คัพ	รอบคัดเลือก	บุนนาเอธิโอเปีย	2–1	0–0	2–1
		รอบแรก	โลบี สตาร์ส	1–1	0–3	1–4
2008	CAF คอนเฟเดอเรชั่น คัพ	รอบคัดเลือก	เอเอส อินเตอร์ สตาร์	1–0	0–1	1–1 (5–4 หน้า )
		รอบแรก	เอเอส วีต้า คลับ	0–0	0–0	0–0 (2–4 หน้า )

^{[ 13 ] [ 14 ]}