בעונת 1990/1991 העפילה הקבוצה לפלייאוף העליון, וסיימה את העונה במקום השישי בטבלה. בעונת עונת 1991/1992 ספגה הקבוצה 43 שערי חובה, מספר שערי החובה הגבוה ביותר של הקבוצה מאז עונת הירידה, עונת 1969/1970. מנגד, הרבתה הקבוצה גם להבקיע, וסיימה את העונה עם 40 שערי זכות, מספר שערי הזכות הגבוה ביותר שלה מאז עונת 1981/1982, וסיימה את העונה במקום העשירי בטבלה.
לקראת עונת 1992/1993 הצטרפו לקבוצה אורי מלמיליאן והישאם זועבי. לאחר חמישה מחזורים פוטר אליהו עופר והוחלף בעוזר המאמן ויקו חדד ובעקבות כך עזב מלמיליאן את הקבוצה. באר שבע הציגה יכולת התקפית טובה במהלך העונה, כשזועבי מסיים כסגן מלך שערי הליגה עם 17 שערים, וקובע שיא כיבושים לשחקן באר שבעי בליגה הבכירה. הקבוצה כולה סיימה את העונה עם 52 שערי זכות, מספר שערי הזכות הגבוה ביותר של הקבוצה אי פעם בעונה אחת בליגה הבכירה, כמו גם עם הפרש השערים הטוב ביותר שלה אי פעם בליגה הבכירה, ובמקום הרביעי בטבלה.
בעונת 1993/1994 שברה הקבוצה שוב את שיא השערים שלה לעונה בליגה הבכירה וכבשה 54 שערים, ושחזרה את הפרש השערים הטוב ביותר שלה עד אז בליגה הבכירה. אמיר אביגדור סיים את העונה כמלך השערים של הקבוצה עם 16 כיבושים, הקבוצה סיימה במקום השלישי וזכתה בכרטיס לגביע אופ"א בפעם הראשונה בה השתתפו קבוצות ישראליות במפעל.
בעונת 1994/1995 מונה ויטלי שבצ'נקו האוקראיני לאימון הקבוצה. בגביע אופ"א הוגרלה הקבוצה מול אריס סלוניקי מיוון, הפסידה לה פעמיים והודחה מהמפעל. בליגה המשיכה הקבוצה להציג יכולת גבוהה, השוותה את שיא שערי הזכות שקבעה בעונה הקודמת, וסיימה בפעם השנייה ברציפות במקום השלישי.
בעונת 1995/1996 מונה שוב ויקו חדד לאימון הקבוצה. בשלב המוקדמות הראשון של גביע אופ"א ניצחה הקבוצה את קיי אף טירנה מאלבניה, ולאחר מכן הודחה מהמפעל לאחר מפגש כפול מול ברצלונה בו הפסידה 0–7 בבית ו-5–0 בחוץ. בהמשך העונה פוטר חדד והוחלף על ידי המאמן הקודם ויטלי שבצ'נקו. הקבוצה זכתה בפעם השנייה בתולדותיה בגביע הטוטו, לאחר ניצחון על הפועל כפר סבא במשחק הגמר. בליגה הציגה הקבוצה יכולת ירודה ומיעטה להבקיע, ושבצ'נקו הוחלף על ידי אלי גוטמן. באר שבע סיימה את העונה כשהיא עם 32 שערי זכות ובמקום העשירי בטבלה.
בעונת 1996/1997 הוביל גוטמן את הקבוצה לזכייה ראשונה בתולדותיה בגביע המדינה, לאחר ניצחון 1–0 על מכבי תל אביב במשחק הגמר, משער של ג'ובאני רוסו. בליגה סיימה הקבוצה את העונה במקום השלישי, לאחר שפספסה את המקום השני במחזור האחרון של העונה, עם 25 שערי חובה ועם הפרש השערים הטוב ביותר בתולדותיה בליגה הבכירה.
בקיץ 1997 החליט הבעלים אלי להב לשחרר רבים מהשחקנים המובילים בקבוצה וביניהם רוסו, סיאד חלילוביץ' ושי הולצמן, ולאחר מכן עזב את הקבוצה והעביר את הבעלות לאלי זינו. בעקבות כך, פתחה הקבוצה את עונת 1997/1998 עם סגל מצומצם. בשל המחסור בשחקנים העלתה הקבוצה את שחקן הנוער יוסי בניון לסגל הקבוצה הבוגרת כבר בגיל 17, ולמאמן מונה בני טבק. בשלב המוקדמות הראשון של גביע אירופה למחזיקות גביע הדיחה הקבוצה את ז'לגיריס וילנה הליטאית, ולאחר מכן הודחה מהמפעל על ידי רודה ההולנדית, לה הפסידה 4–1 בבית ו-10–0 בחוץ. לאחר התבוסה התפטר טבק, ובמקומו מונה שוב ג'קי דקל, שפוטר אחריי מספר מחזורים ובמקומו מונה אליהו עופר שכמעט והשאיר את הקבוצה בליגה. יוסי בניון הבקיע 15 שערים בעונה זו, כולל שער דרמטי בניצחון 1–0 על מכבי חיפה במחזור הסיום, אך עקב ניצחונה של יריבתה לתחתית בני יהודה תל אביב ירדה הקבוצה לליגת המשנה לאחר 27 שנים רצופות בליגה הבכירה, כשהיא מסיימת את העונה עם 57 שערי חובה, מספר שערי החובה הגבוה בתולדותיה בעונה אחת בליגה הבכירה.
לקראת עונת 1998/1999 בליגת המשנה מונה שייע פייגנבוים למאמן הקבוצה, ובמהלך העונה הוחלף על ידי גילי לנדאו. הקבוצה נאבקה עם מכבי נתניה על ההעפלה לליגת העל, אך לבסוף סיימה במקום השלישי בטבלה.
תחילת שנות האלפיים.
לקראת עונת 1999/2000 חזר אליהו עופר לאימון הקבוצה, ולאחר מכן הוחלף במוטי איווניר. לקראת סיום העונה הוחלף איווניר באייל לחמן, והקבוצה נכשלה שוב בניסיונה להעפיל לליגה הראשונה, לאחר שסיימה במקום השביעי בטבלה, בעת שיריבתה העירונית בית"ר באר שבע במקום החמישי ומעליה בטבלה.
בעונת 2000/2001 המשיך אייל לחמן על הקווים, אך הוא פוטר במהלך העונה, והוחלף על ידי שלמה שרף, שהתפטר לאחר שני מחזורים, ולופא קדוש החליף אותו בתפקיד ותחתיו הפועל באר שבע חזרה לצמרת הליגה הלאומית להילחם על עלייה לליגת העל, בעונה זו נפגשה הקבוצה מול בית"ר ירושלים מליגת העל במסגרת גביע המדינה, וניצחה 3–2 לאחר הארכה. במחזור האחרון של העונה נפגשה הפועל באר שבע מול הפועל רמת גן על משחק העלייה לליגה הראשונה, ובו ניצחה 5–0 והבטיחה את עלייתה לליגת העל מהמקום הראשון.
בשתי העונות הראשונות לאחר חזרתה לליגת העל סיימה הקבוצה פעמיים במקום החמישי, ובעונת 2002/2003 אף הגיעה למעמד גמר גביע המדינה, לאחר שחלפה בשמינית גמר על פני הפועל תל אביב עם ניצחון 1–0 בבלומפילד, ובחצי גמר ניצחה 3–0 מכבי חיפה. בגמר פגשה הפועל באר שבע את הפועל רמת גן מהליגה הלאומית, אך נוצחה בבעיטות הכרעה מ-11 מטר לאחר 1–1 בתום ההארכה.
בעונת 2003/2004 חזר אלי גוטמן לתפקיד המאמן, ובסגל הקבוצה בלטו אלון מזרחי, דדי בן-דיין, אופיר חיים, ובלסינג קאקו. בעונה זו סיימה באר שבע במקום הרביעי אשר הקנה לה כרטיס למפעל גביע האינטרטוטו.
בעונת 2004/2005 נקלעה הקבוצה לבעיות כלכליות ובסיומה נשרה הקבוצה לליגה הלאומית לאחר שרוב שחקני הסגל שוחררו. הבעיות הכלכליות המשיכו ללוות את הקבוצה גם בשתי העונות הבאות, בהן סיימה במקום הרביעי בליגה הלאומית.
תחילת עידן אלונה ברקת.
ביולי 2007 רכשה אשת העסקים אלונה ברקת את הקבוצה מידיו של אלי זינו. ב-29 באוגוסט 2007, במהלך משחק אימון נגד מכבי באר שבע, קרס חלוצה של הקבוצה צ'אסווה נסופוואה ומת כתוצאה מדום לב.
בעונה הראשונה בעידן אלונה ברקת, עונת 2007/2008, סיימה הקבוצה במקום הרביעי בליגה הלאומית ולא הצליחה להעפיל לליגת העל. בעונת 2008/2009 מונה גיא לוי למאמן הקבוצה, והוחתם הקשר ההתקפי מאור מליקסון. בעונה זו הצליחה הקבוצה לשוב לליגת העל לאחר ארבע שנים בליגה הלאומית. באותה עונה זכתה הקבוצה גביע הטוטו לליגה הלאומית, לאחר שגברה בגמר 1–0 בהארכה על מכבי הרצליה.
לקראת עונת 2009/2010 מונה גיא עזורי למאמן הקבוצה, אשר החתים בקבוצה מספר שחקנים חדשים, ביניהם דוד רביבו, סיראז' נסאר וויליאם סוארס הברזילאי שהצטרף בינואר. הקבוצה הציגה יכולת חלשה ואוהדיה מחו ודרשו את התפטרותו של עזורי. במרץ 2010, בעקבות תקרית אלימה של אוהד כלפי המאמן, החליט עזורי להתפטר מתפקידו. הבעלים ברקת הודיעה שבעקבות התנהגות האוהדים היא תעזוב את הקבוצה בתום העונה. האוהדים פתחו בקמפיין להשארתה במועדון, ובסופו של דבר נשארה ברקת בהפועל באר שבע. המנהל המקצועי של מחלקת הנוער, ויקו חדד, שימש כמאמן עד סוף העונה, בה סיימה הקבוצה במקום התשיעי.
בעונת 2010/2011 מונה ניר קלינגר למאמן הקבוצה. הקבוצה התחילה את העונה בצורה טובה, אך בינואר 2011 נמכר כוכב הקבוצה מאור מליקסון לויסלה קרקוב, ולאחר מכן חלה ירידה משמעותית ביכולתה. במחזור האחרון של העונה הסדירה הצליחה להעפיל לפלייאוף האמצעי, לאחר ניצחון חוץ 2–0 על מכבי תל אביב, ואת העונה סיימה בפעם השנייה ברציפות במקום התשיעי.
בעונת 2011/2012 החליטה הבעלים אלונה ברקת, להתבסס על שחקני בית צעירים, ביניהם המגן השמאלי אופיר דוידזאדה, בשילוב שחקנים מנוסים, אך העונה נפתחה בצורה רעה, כאשר הקבוצה הפסידה שישה משחקים רצופים. במחזור השביעי ניצחה הקבוצה 0–2 את הפועל חיפה, ובתום המשחק החליט קלינגר להתפטר. במקומו מונה גיא לוי שחזר לקדנציה נוספת כמאמן הקבוצה, וחתם על חוזה עד תום העונה. במחזור האחרון ניצחה הקבוצה בבית 3–1 את בית"ר ירושלים, ובעקבות כך סיימה במקום ה-13 ונשארה בליגת העל.
בעונת 2012/2013 החתימה הבעלים אלונה ברקת את המאמן היוצא של מכבי חיפה אלישע לוי. בעונה זו החתימו שוער בכיר בדמותו של אוסטין אג'ידה. באותה עונה הגיעה הקבוצה למעמד גמר גביע הטוטו מול הפועל חיפה והפסידה בהארכה 0–1, כאשר עידו אקסברד חלוץ הפועל באר שבע החטיא פנדל בדקה 88. בעונה זו הגיעה הקבוצה לפלייאוף התחתון, וניצלה מירידה רק במחזור האחרון, לאחר ניצחון חוץ 3–0 על מכבי נתניה. בעקבות הניצחון סיימה באר שבע במקום השמיני, והנחילה למכבי נתניה ירידת ליגה.
החזרה לצמרת.
לקראת עונת 2013/2014 החליטה הבעלים אלונה ברקת להחתים לעונה נוספת את אלישע לוי, ולצרף שחקנים בעלי שם ופוטנציאל לעתיד, בעקבות כך הגדילה אלונה ברקת את התקציב בהתאם והחתימה שחקנים בכירים בדמותם של אליניב ברדה, מאור בוזגלו, וגליינור פלט. החתמות אלו הובילו את הקבוצה לעונה הטובה ביותר שלה מאז עונות האליפות, וסיימה את העונה במקום השני. בעקבות כך המועדון קיבל כרטיס למוקדמות הליגה האירופית.