האזכור הראשון לאגודת הפועל ירושלים הוא בכינוס הפועל הרביעי בשנת 1935. היה זה הכינוס הראשון בו נערכו משחקי כדורסל ומבין ארבע קבוצות שהשתתפו בתחרות (ירושלים, תל אביב, יהודה ושומרון) סיימה ירושלים במקום הראשון אחרי ניצחון בגמר על יהודה בתוצאה 4:8. עם זאת, הסיפור האמיתי של המועדון מתחיל בשנת 1943 באולם ברחוב ההסתדרות בטורנירים שונים ומשחקי ידידות. הקבוצה התכנסה בין פעם לפעמיים בשבוע, לעיתים תחת הדרכתו של זאב לבנדל ולעיתים בלי מאמן. כוכב הפועל ירושלים (בכדורסל ובכדורגל) לפני קום המדינה היה יהושע וייסמן, שהופיע בנבחרת הראשונה של ארץ ישראל בכדורסל בפסטיבל הדמוקרטי בפראג בשנת 1947. הוא נפל באותה שנה במלחמת השחרור בדרך לעטרות. במלחמת השחרור הופסקה פעילות האגודה אבל היא חודשה מייד עם סיום המלחמה תוך שהקבוצה עוברת להתאמן באולם ימק"א. לאגודה הצטרפו האחים מרק וסמי ממרן, שהגיעו לארץ במסגרת עליית כדורסלנים ממצרים. בתחילת שנות ה-50 החל להדריך את הקבוצה ארי זמרי, לימים עיתונאי ספורט. באמצע העשור שודרגו התנאים של הקבוצה, שעברה לשחק ולהתאמן באולם ברחוב שטראוס, שהיה בזמנו האולם המקורה היחיד בארץ.

העשור של שנות השישים האיר פנים לירושלים, בעיקר בזכות הצלחת הקבוצה בשמירה על הבית. כאמור, האולם בשטראוס היה האולם המקורה היחיד בארץ והקבוצה התקשתה במשחקי החוץ במגרשים הפתוחים. לעומת זאת במשחקי הבית הסיפור היה שונה לחלוטין - חמש מאות צופים היו נדחסים לאולם הקטן בכל ערב שישי ודוחפים את הקבוצה לניצחונות גדולים על אריות הליגה דאז: הפועל ומכבי תל אביב, גבעת ברנר והפועל חיפה. דוד קמינסקי היה המנהיג הבלתי מעורער של הקבוצה בין השנים 1956-1958, שאף נחשב לגדול שחקני הקבוצה מאז היווסדה. בעונת 1960/61 הוביל קמינסקי את הפועל ירושלים למקום הרביעי בליגה. עונת 1962/63 סימנה את סוף דרכו של קמינסקי בהפועל ירושלים ודריכתו של כוכב חדש - ישראל ברלינסקי (אמיר). בתחילת העונה הצטרפו לקבוצה שני שחקנים אמריקאיים - פאריס וסוקניק - סטודנטים שהגיעו לשנת השתלמות, והם בעצם היו שחקני החיזוק ה"זרים" הראשונים שלנו.

השנים 1981-1986 היו שנים קשות עבור הקבוצה, שנתקעה שש שנים בליגה הארצית, זאת למרות שתחת הדרכתו של יהושע רוזין הקבוצה סיימה ראשונה שלוש עונות ברציפות. נקודת האור היחידה בשנים האלו הייתה בנייתו של האולם במלחה, אשר הפך למגרש הבית של הקבוצה במקום האולם העתיק ברחוב שטראוס. חציו השני של העשור התאפיין בתקיעת יתד של הקבוצה בליגה הלאומית. לראשונה בתולדות הפועל הוחתם מאמן זר - פארוק קולאנוביץ'. כמו כן הוחזר לקבוצה מי שיהפוך בהמשך לאחד הקלעים הגדולים בתולדותיה - דורון שפע. בנוסף הגיעו לבירה מייק קרטר, גרי גרהאם ודייויד בלאקוול. לראשונה זה שנים רבות, הקבוצה לא נאלצה להיאבק נגד הירידה.

העשור של שנות התשעים היה תור הזהב של המועדון. בניצוחם של שפע, חזן, בלאקוול, מוקי מוטאפצ'יץ', דייויד בלאט, גרג קולינס ופיני לוי הקבוצה סיימה את עונת 90/91 במקום הרביעי. מי שהוביל את הקבוצה באותם ימים היה הרכז הצעיר בשם... עדי גורדון. בקיץ 1995 חלה התפתחות ששינתה את פניה של הפועל. איש העסקים נחום מנבר העביר את תמיכתו לירושלים. גורדון, שפע וקולמן חזרו לקבוצה ויצרו הרכב חזק מאוד יחד עם בילי תומפסון ופפי תורג'מן, תחת המאמן פיני גרשון. הפועל הגיעה לגמר הגביע, בו עדי גורדון זרק את ג'מצ'י לכיוון אחד, את ליף לכיוון השני, ולבסוף נתן "קטנה" מעל תום צ'יימברס. הכדור ראה רק רשת, הפועל ניצחה 65:67 וזכתה בגביע הראשון בתולדותיה. שנה לאחר מכן ההישג שוחזר עם זכייה שנייה ברציפות.

עונת 2003-04 היתה הישג השיא של המועדון באירופה. תחת המאמן שרון דרוקר, יחד עם חבורה של לוחמים שכללה את ארז כץ, דורון שפר, וויל סולומון, טונג'י אווג'ובי וקלי מקארתי, הפועל הגיעה לגמר גביע היול"ב בשרלרואה מול ריאל מדריד. אלפי אוהדים ירושלמים מילאו את האולם, והפועל זכתה בגביע היסטורי - גביע היול"ב 03/04. בעונת 2007/08, האדומים הציגו את אחד המהפכים הגדולים בגמר הגביע אי פעם מול מכבי ת"א. פיגור של 22 נקודות הפך לניצחון 89:93 בראשות ג'יימי ארנולד (29 נק'), טימי באוורס ודרור חג'ג'. מכבי ת"א החליטה לרדת מהפרקט ולא להשתתף בטקס ההנפה.

עונת 14/15 בישרה על המעבר לבית החדש - הארנה. בסיס האוהדים גדל דרמטית והסגל כלל את יותם הלפרין וליאור אליהו. באותה עונה זכתה הפועל באליפות ראשונה בתולדות המועדון אחרי ניצחון על הפועל אילת. בעונת 16/17 נחת במועדון אמארה סטודמאייר, כוכב ה-NBA, והוביל יחד עם ג'רום דייסון, קרטיס ג׳רלס, טרנס קינזי וסימונה פיאנג'ני לאליפות השנייה בתולדות המועדון ולהופעה בלתי נשכחת בחצי גמר היורוקאפ. לאחר מכן, עם עודד קטש, זכתה הפועל בשני גביעים רצופים (18/19 ו-19/20).

מגפת הקורונה ומבצע "שומר החומות" הרחיקו אותנו מהקהל וגרמו לעזיבת זרים, אך אחד מהניצחונות שייזכרו הוא על מכבי ת"א עם סגל אלמוני, בזכות שלשת ניצחון אדירה של אדם אריאל 83:82. בתקופה זו המועדון החליף מאמנים ונתן הזדמנויות לצעירים כמו יונתן אלון ויותם הלפרין.

אלכסנדר דז'יקיץ' העמיד סגל לוחם שהפך לאחת מקבוצות ההגנה הטובות אי פעם. הקבוצה זכתה בגביע המדינה והגיעה לגמר ליגת האלופות. שיא הקהל בארנה נשבר (11,600 צופים) בניצחון על אא"ק אתונה. 5,000 אדומים ליוו את הקבוצה לפיינל פור במלאגה.

ביוני 2023 השלים מתן אדלסון את רכישת הפועל. העונה נצבעה בסימן אירועי השבעה באוקטובר, והמועדון נעמד לצד המשפחות השכולות. במאי 24 זכתה הקבוצה בגביע המדינה בפעם השנייה ברצף. המורשת נמשכת.