האימפריה האדומה נוסדה ב-1949 ע"י זלמן כספי, שחקן עבר של הפועל רמת-גן.
הקבוצה שיחקה 3 שנים בליגה הסדירה ופעילותה הופסקה לאחר שהוחלט בהתאחדות כי המרחק הגדול אינו מאפשר את השתתפותה. הקבוצה הוקמה מחדש בשנת 1955 ודשדשה בליגה א' (השנייה דאז) עד שעלתה לליגה הלאומית בשנת 1965.
שנות השבעים
בשנת 1970 ירדה לליגה א' ושבה לליגה העליונה מיד לאחר שנה אחת.
שנות השיא של המועדון היו בעונות 1974/5 ו-1975/6.
המועדון תחת שרביטו של המאמן אמציה לבקוביץ' זכה בשתי אליפויות רצופות, תוך הצגת כדורגל התקפי, משוחרר ומלהיב. השחקנים הבולטים בעונות האליפות היו השוער רוני מוסקוביץ', המגינים אורי בנימין ויעקב כהן, הבלם אלון בן דור, הקשרים מאיר ברד ואליהו עופר והחלוצים אברהם נומה ושלום אביטן הידוע בכינויו "הפה הגדול". בשנת 1976, היו הפועל באר שבע ובית"ר ירושלים הקבוצות הראשונות בתולדות הכדורגל הישראלי ששיחקו במפעל אירופאי, גביע האינטרטוטו.
בין היתר פגשו האדומים את מועדון הפאר הגרמני הרטה ברלין ואת סטנדארד ליאז' הבלגית.
את סוף שנות ה-70 בילה המועדון במרכז הטבלה והתרפק על הישגיו בשנים קודמות.
למעלה: דור האליפות. באמצע: משחק באיצטדיון העירוני. למטה: נומה נוגח לשער.
שנות השמונים
גם בשנים הראשונות בשנות ה-80 התברג המועדון במרכז הטבלה ללא הישגים מיוחדים.
בשנת 1984 הצליחה באר-שבע להעפיל לגמר גביע המדינה, שם נוצחה בפנדלים ע"י הפועל לוד. את הפנדל המכריע החמיץ רפי אליהו, כאשר בהמשך נוכל לראות שהתפוח נפל קרוב מאוד לעץ.
הישג בולט נוסף בשנים אלו היה זכייה בגביע הטוטו בשנת 1988/9 לאחר ניצחון על מכבי נתניה.
שנות התשעים
שנות התשעים התאפיינו במספר הישגים מרשימים לצד כישלונות שכולנו רוצים לשכוח.
בין השנים 1990-1997 היתה הפועל באר-שבע חברה קבועה בצמרת הליגה הלאומית הראשונה.
בשנים אלה הצליחה הקבוצה להשיג 3 פעמים את הכרטיס למפעל אירופאי., פעמיים גביע אופ"א ופעם נוספת בגביע אירופה למחזיקות גביע. תחילת הדרך בגביע אופ"א החלה באוגוסט 2004 כשהאדומים פגשו את אריס סלוניקי היוונית, ובסיום 2 המפגשים היתה רגלם של היוונים על העליונה.
שנה מאוחר יותר שוב השיגה הקבוצה את הכרטיס לגביע אופ"א שם פגשה במוקדמות את טיראנה האלבנית והצליחה לגבור עליה במפגש כפול, שסידר לויקו חדד ולחניכיו עימות חזיתי עם יוהאן קרויף וברצלונה הגדולה. בספטמבר 1995 הגיעו הקטלונים לוסרמיל עם סוללת כוכבים וביניהם לואיס פיגו, איבן דלה-פניה, ג'ורדי קרויף ומהו קודרו. תוצאת הסיום 7:0 לספרדים. בגומלין הסתפקה ברצלונה בניצחון 0:5 והשאירה את הפועל באר-שבע בעיקר עם זכרונות.
בסיום אותה עונה, 1995/6, הצליחה הקבוצה לזכות בגביע הטוטו בפעם השנייה לאחר ניצחון בגמר על הפועל כפר-סבא. עונת 1996/7 חרוטה בזכרונו של כל אוהד. הקבוצה בהנהגתו של אלי גוטמן הצליחה לזכות בגביע המדינה היחיד בתולדות המועדון לאחר ניצחון בגמר על הכבשה השחורה של המועדון באותם שנים, מכבי ת"א. אותה עונה תיזכר בעיקר עקב התצוגות הגדולות והכדורגל המלהיב אותו הציגה הקבוצה בכיכובם של ה-"קוסם" סיאד חלילוביץ' ושל ג'ובני רוסו.
בסיום אותה עונה החליט הבעלים דאז אלי להב לבצע מכירת חיסול ושיחרר מהקבוצה את כל סוללת הכוכבים וביניהם חלילוביץ', רוסו, הולצמן, סולוב, בסיס וחזות. להב עזב את הקבוצה והעביר את הבעלות לאלי זינו במהלך פתיחת העונה העוקבת. עקב "מכירת החיסול" פתחה הפועל באר-שבע את עונת 1997/8 עם סגל מצומצם וחלש, ולראיה זה בא לידי ביטוי בתבוסה המשפילה 10:0 לרודה ההולנדית במסגרת גביע אירופה למחזיקות. בסיום אותה עונה נשרה הקבוצה לליגת המשנה לאחר 27 שנים רצופות בליגה הבכירה. הירידה לליגה השנייה התקבלה בעיר באר-שבע בצורה קשה מאוד ואבל כבד נפל על העיר כולה, שהתקשתה להתאושש מהמפלה.
שנות ה-2000
לאחר 3 שנים מייגעות בליגת המשנה הצליחה הקבוצה, תחת הדרכתו של לופא קדוש, להעפיל לליגת העל בסיום עונת 2000/1. לאחר העלייה הצליחה הקבוצה לתקוע יתד בצמרת ליגת העל ואף בעונת 2002/3 העפילה לגמר גביע המדינה, בו נוצחה בפנדלים ע"י הפועל רמת-גן האלמונית מהליגה השנייה. מעל 20,000 אוהדים ליוו את הקבוצה לאצטדיון רמת-גן והיו שותפים לעוד רגע עצוב בתולדות המועדון. לאחר 4 שנים מוצלחות בליגת העל הגיעה הנפילה. בסיום עונת 2004/5 נשרה הקבוצה בפעם השנייה לליגת המשנה לאחר עונה עלובה אותה סיימה הקבוצה במקום האחרון בטבלה. לאחר הירידה התדרדר מצבה של הקבוצה והתגלו בעיות כלכליות קשות. הבעלים אלי זינו לא היה מסוגל להעמיד קבוצה ראויה שתתמודד על עלייה לליגה הבכירה. במשך 3 שנים רצופות הוחלפו המון מאמנים, שחקנים רבים עזבו את המועדון, מס' שחקנים הואשמו בהטיית משחקים ובמועדון שררה אוירת נכאים. בסיום עונת 2006/7 היה המועדון על סף קריסה כלכלית, עד שבחודש יולי 2007 הגיעה הישועה. אשת העסקים אלונה ברקת רכשה את הקבוצה מידיו של אלי זינו ובאופן רשמי הקבוצה עברה לבעלותה ב-11.7.07. עונת 2007/8 נפתחה בצל העיכובים בהעברת הבעלות לברקת ואף בפתיחת העונה איבדה הקבוצה את חלוצה הזמבי צ'סוואה נספוואה שקיבל דום לב במהלך משחק אימון. העונה היתה צולעת מאוד ובסיומה לא הצליחה הקבוצה לעלות לליגת העל. שנה מאוחר יותר, עם הכנה מסודרת לליגה והחתמה נכונה של שחקני רכש,
הצליחו האדומים בראשות גיא לוי לשוב לליגת העל בתקווה להישאר שם עוד שנים רבות. באותה עונה הצליחה הקבוצה לזכות בגביע הטוטו של הליגה הלאומית ולצרף גביע נוסף לארון הגביעים שהכיל גביע מדינה אחד ו-3 גביע טוטו.
