בעונת 2008/09, מעפילה הפועל באר-שבע תחת שרביטו של המאמן גיא לוי, בחזרה לליגת העל. הקבוצה גם זוכה בגביע הטוטו לליגה הלאומית באותה עונה, לאחר ניצחון 1-0 בהארכה על מכבי הרצליה.
תקיעת היתד המחודשת בליגת העל לא הייתה פשוטה עבור באר-שבע, כאשר היא חווה עם עלייתה עונה אחת במרכז הטבלה ולאחר מכן שתי עונות בהן הקבוצה שורדת במחזור האחרון בליגה; בפעם הראשונה לאחר ניצחון ביתי 3-1 על בית"ר ירושלים ובפעם השנייה לאחר ניצחון חוץ 3-0 בקרב הישרדות ישיר מול מכבי נתניה.
לאחר מלחמות ההישרדות, זכתה הקבוצה לשתי עונות מהמוצלחות בהיסטורית המועדון, תחת הובלת המאמן אלישע לוי.