את עונת 1973/1974 פתחה הקבוצה בצורה לא טובה, ובתום 18 מחזורים התמקמה במקום ה-14 בליגה, אך עם התקדמות הליגה הצליחה להשתפר, ולסיים את העונה במקום השביעי בטבלה. בנוסף, הגיעה הקבוצה שוב לרבע גמר גביע המדינה, בו הפסידה 1–3 להפועל פתח תקווה בסיכום שני משחקים.
תארים ראשונים.
בעונת 1974/1975 מונה אמציה לבקוביץ' למאמן הקבוצה כאשר הוא בן 37, ונחשב למאמן צעיר ביחס למאמנים הבכירים והמובילים בארץ. לבקוביץ' היה המאמן הראשון שהחדיר את סגנון המשחק של המגנים התוקפים בישראל, סגנון אשר נלקח מהכדורגל הגרמני. לבקוביץ' שילב בהרכב הקבוצה שחקנים צעירים, בהם אורי בנימין בן ה-20 כמגן ימני ויעקב כהן בן ה-18 כמגן שמאלי. סגל הקבוצה היה מהצעירים בליגה, וכלל בתוכו רק ארבעה שחקנים שעברו את גיל 25. הקבוצה התחילה את העונה עם שלושה ניצחונות, כולל ניצחון על אלופת העונה שעברה מכבי נתניה, מבלי לספוג ולו שער אחד. במהלך העונה התמודדה על האליפות מול מכבי נתניה, וההכרעה הגיעה מחזור אחד לפני סיום העונה. באר שבע שיחקה מול מכבי יפו, כאשר נקודה אחת מפרידה בינה לבין מכבי נתניה מהמקום השני, וניצחה 1–0 משער של אפרים צבי הפועל באר שבע הוכתרה לאלופת המדינה בכדורגל לראשונה בתולדותיה, כאשר מרבית שחקני הסגל היו שחקני בית. אפרים צבי סיים את העונה כמלך השערים של הקבוצה עם 10 כיבושים, ואורי בנימין זכה בתואר כדורגלן העונה בישראל.
בקיץ 1975 השתתפה הקבוצה במשחק אלוף האלופים לראשונה בתולדותיה, וזכתה בתואר לאחר ניצחון 2–1 על הפועל כפר סבא.
בעונת 1975/1976 פתחה הפועל באר שבע את הליגה בצורה מאכזבת כאשר סיימה פעמיים בתיקו בשני המחזורים הראשונים, אולם במחזורים הבאים השתפרה, וכבר במחזור החמישי התמקמה לראשונה בעונה זו במקום הראשון בטבלה. במהלך העונה נאבקה על המקום הראשון מול בית"ר ירושלים, ובמחזור הנעילה פגשה באר שבע שוב את מכבי יפו למשחק מכריע, כשהפעם נלחמה יפו נגד הירידה והייתה חייבת לנצח על מנת להישאר בליגה, בעוד באר שבע רצתה לנצח כדי להבטיח את האליפות. מנגד, פגשה בית"ר ירושלים את מכבי תל אביב, שנלחמה גם היא נגד הירידה, והייתה חייבת לנצח. מכבי יפו ניצחה 1–0, אך בעקבות הפסדה של בית"ר ירושלים השיגה הפועל באר שבע אליפות שנייה ברציפות. שלום אביטן, שחזר לקבוצה בתחילת העונה, סיים אותה כמלך השערים של הקבוצה עם 11 כיבושים.
בקיץ 1976 היו הפועל באר שבע ובית"ר ירושלים הקבוצות הראשונות בתולדות הכדורגל הישראלי ששיחקו במפעל אירופאי, גביע האינטרטוטו. באר שבע הוגרלה לבית ב' וקיימה שישה משחקים בשיטת "בית-חוץ" נגד הקבוצות קוגה מדנמרק, הרטה ברלין מגרמניה וסטנדרד ליאז' מבלגיה. מאזן הקבוצה במפעל היה ניצחון אחד, 2–1 על קוגה באצטדיון וסרמיל, שלוש תוצאות תיקו ושני הפסדים. בהמשך השתתפה בפעם השנייה ברציפות במשחק אלוף האלופים, בו הפסידה למחזיקת הגביע בית"ר ירושלים 2–3 לאחר הארכה.
סוף שנות השבעים.
בעונת 1976/1977 כמעט הפכה הפועל באר שבע לאלופה מכהנת ראשונה שיורדת ליגה. תחת הדרכתו של אלי פוקס, ששב לאימון הקבוצה, פתחה באר שבע רע את העונה ונקלעה לתחתית. בעקבות כך, לאחר 16 מחזורים התפטר פוקס מאימון הקבוצה, ואליהו עופר, שפרש מפעילות סדירה כשחקן במהלך העונה ושימש גם כעוזרו של פוקס, נקרא לתפקיד המאמן. שני מחזורים לסיום העונה נפגשה הקבוצה בחוץ עם מכבי חיפה למשחק הישרדות, כשרק הפרש שערים מפריד בין שתי הקבוצות בטבלה. הפועל באר שבע ניצחה 1–0 והצליחה להישאר בליגה בעוד מכבי חיפה ירדה לליגת המשנה. בנוסף, הגיעה הקבוצה שוב לרבע גמר גביע המדינה, לאחר שניצחה 2–0 את מכבי חיפה בתוצאה בשמינית הגמר, והודחה לאחר הפסד 0–3 לבית"ר תל אביב.
בעונת 1977/1978 הציגה הקבוצה יכולת התקפית טובה לאורך כל העונה, בניצוחם של מלך השערים שלה שלום אביטן, עם 12 שערים וסגנו ויקטור סרוסי, עם 10 שערים, אך לצד זאת הציגה יכולת הגנתית פחות טובה. באר שבע סיימה את העונה כשהיא במקום החמישי בטבלה עם 43 שערי זכות, המספר הגבוה ביותר בעונה אחת בתולדותיה של הקבוצה בליגה הראשונה עד אז (מלבד העונה הכפולה של 1966/1968, בה הובקעו 71 שערים).
את עונת 1978/79 סיימה הקבוצה במקום התשיעי. בנוסף, הגיעה בפעם השישית בתולדותיה למעמד רבע גמר גביע המדינה, לאחר ניצחון 2–1 על הפועל כפר סבא בשמינית הגמר. ברבע הגמר הפסידה לבית"ר תל אביב בבעיטות הכרעה.
שנות השמונים.
לקראת עונת 1979/1980 שב אמציה לבקוביץ' לאימון הקבוצה, והצטרף אליה אפרים דוידי הצעיר ממכבי באר שבע. הקבוצה לא פתחה טוב את העונה לאחר מכן נתן לבקוביץ' הזדמנות לשחקני הגנה צעירים נוספים. מספר שערי החובה, 27, היה הנמוך ביותר מאז עונת האליפות הראשונה תחת לבקוביץ' (1974/1975), אך ההתקפה לקתה בחסר והקבוצה מיעטה לכבוש שערים. את העונה סיימה הקבוצה במקום העשירי בטבלה עם שבעה ניצחונות בלבד.
לקראת עונת 1980/1981 חזר אליהו עופר לעמדת המאמן והיא פתחה היטב את העונה, אולם כשם שהרבתה הקבוצה להבקיע שערים כך גם הרבתה לספוג, והיא סיימה את העונה כשהיא במקום ה-11 בטבלה.
לקראת עונת 1981/1982 מינתה הקבוצה את שמעון שנהר, והקבוצה פתחה את העונה עם ארבעה הפסדים, שתי תוצאות תיקו וניצחון, שהובילו למקום ה-15 והלפני אחרון בליגה. מהמחזור השמיני ואילך השיגה הקבוצה רצף של 11 מחזורים ללא הפסד ובתום המחזור ה-18 התמקמה הקבוצה במקום הרביעי בטבלה, עליו הצליחה לשמור עד סוף העונה.
באר שבע הציגה יכולת התקפית טובה במהלך העונה, הבקיעה 43 שערי זכות, והשוותה בכך את שיא הכיבושים לעונה אחת. מלך שערי הקבוצה היה שלום אביטן עם 14 שערים. בנוסף, הגיעה הקבוצה בפעם השנייה בתולדותיה לחצי גמר גביע המדינה, לאחר שניצחה בשמינית הגמר 1–0 את מכבי נתניה, וברבע הגמר ניצחה 4–0 את הכח רמת גן. בחצי הגמר פגשה את הפועל תל אביב והפסידה 3–5 בבעיטות הכרעה לאחר 2–2 בתום ההארכה.
המקום הרביעי בליגה הקנה לבאר שבע כרטיס לגביע ליליאן, טורניר אשר שוחק בשנות ה-80. לקראת עונת 1982/1983 שיחקה הקבוצה בטורניר ונוצחה בגמר 1–3 מול מכבי נתניה. בעונה זו הציגה באר שבע יכולת הגנתית טובה מאוד וספגה 23 שערי חובה בלבד, מספר שערי החובה הנמוך ביותר מאז עונת האליפות הראשונה. את העונה סיימה באר שבע במקום השלישי בטבלה, ומלך שעריה היה שוב שלום אביטן עם 11 כיבושים.
לקראת עונת 1983/1984 שב אליהו עופר לתפקיד המאמן. הקבוצה שיחקה שוב מול מכבי נתניה בגמר גביע ליליאן והפסידה 2–3. בליגה לא הצליחה הקבוצה לשמור על יציבות, התנדנדה לאורך כל העונה בין אמצע הטבלה לתחתית, ולבסוף סיימה במקום השביעי בטבלה. בנוסף, הגיעה לראשונה בתולדותיה לגמר גביע המדינה, לאחר שניצחה ברבע הגמר 4–2 את הפועל תל אביב בבעיטות הכרעה לאחר משחק חוזר, ובחצי הגמר ניצחה 2–0 את האלופה היוצאת מכבי נתניה. בגמר הפסידה הקבוצה 2–3 בבעיטות הכרעה להפועל לוד, לאחר 0–0 בתום ההארכה.
לקראת עונת 1984/1985 מונה צבי רוזן לתפקיד מאמן הקבוצה, שמיעטה לכבוש שערים וסיימה את העונה עם מספר הכיבושים הנמוך ביותר מאז עונת 1976/1977, ועמדה בפני סכנת ירידה לליגת המשנה. שלושה מחזורים לסיום העונה, בפיגור של 5 נקודות מהמקום בו נשארים ליגה, פוטר רוזן ובמקומו מונה שחקן העבר של הקבוצה ג'קי דקל, שהצליח להשאיר את הקבוצה בליגה הבכירה.
לקראת עונת 1985/1986 מונה נחום סטלמך לתפקיד המאמן, ולעוזרו מונה שחקן העבר של הקבוצה אלון בן דור. בעונה זו הגיעה הקבוצה לראשונה בתולדותיה למעמד גמר גביע הטוטו, לאחר שניצחה בחצי הגמר 2–1 את מכבי תל אביב. בגמר הפסידה 1–2 להפועל פתח תקווה. בליגה מיעטה הקבוצה לספוג שערים וסיימה את העונה עם 24 שערי חובה, אך גם מיעטה להבקיע וסיימה עם 24 שערי זכות, המספר הנמוך ביותר מאז עונת הירידה של 1969/1970. לאורך כל העונה נדדה הקבוצה בין התחתית לאמצע הטבלה, וסיימה לבסוף במקום השמיני בטבלה.
לקראת עונת 1986/1987 מונה נינו ברגיג למאמן הקבוצה, שהחלה את העונה עם שני הפסדים ותיקו. בעקבות כך פוטר ברגיג ובמקומו מונה דרור בר-נור, אשר תחתיו שיפרה הקבוצה את משחק ההגנה, והיא סיימה אותה עם 19 שערי חובה בלבד, אך מנגד המשיכה להתקשות במשחק ההתקפה, מיעטה להבקיע, וסיימה את העונה עם 20 שערי זכות בלבד. מספר שערי הזכות והחובה של הקבוצה היו הנמוכים בתולדותיה בליגה הראשונה. במהלך כל העונה נאבקה בתחתית, וסיימה אותה במקום ה-11 בטבלה.
לקראת עונת 1987/1988 מינתה הקבוצה את ניסים בכר לתפקיד המאמן. בעונה זו שמרה הקבוצה על יכולת הגנתית גבוהה, ושיפרה את היכולת ההתקפית שלה. את העונה סיימה הקבוצה במקום השלישי בטבלה וזכתה בכרטיס לגביע ליליאן בפעם השלישית מאז הוקם הטורניר.
לקראת עונת 1988/1989 ניצחה הקבוצה 1–0 את הפועל תל אביב בגמר גביע ליליאן. בהמשך העונה הגיעה הקבוצה בפעם השנייה למעמד גמר גביע הטוטו, וזכתה בגביע לראשונה בתולדותיה לאחר ניצחון על מכבי נתניה. בליגה הקבוצה לא הרשימה, ובמחזור ה-22 נפרדה מהמאמן ניסים בכר, כשבמקומו הגיע שמעון שנהר לקדנציה שנייה כמאמן הקבוצה. באר שבע מיעטה להבקיע במהלך העונה, עם 22 שערי זכות בלבד, לצד 29 שערי חובה, וסיימה את העונה במקום החמישי בטבלה.
שנות התשעים.
עונת 1989/1990 הייתה העונה הראשונה בה הותר לשתף שחקנים זרים בליגה הישראלית, ובאר שבע צירפה את שחקני ההתקפה הארגנטינאים קלאודיו דיקסטרה וריקרדו קאצ'יונה. במהלך העונה החליפה הקבוצה ארבעה מאמנים: שמעון שנהר שסיים את דרכו במחזור החמישי, שחקני העבר חיים כהן ואלון בן דור, ואליהו עופר שמונה לקראת תום העונה בה סיימה הקבוצה במקום התשיעי בליגה.