ה-FIS איגדה בתוכה מגוון רחב של תומכים באסלאם, שהתבטא בשני מנהיגיה. נשיאה, עבאסי מדאני, פרופסור ולוחם לעצמאות אלג'יריה כנגד השלטון הצרפתי ייצג דעות דתיות מתונות, וסימל את הקשר של המפלגה אל מלחמת העצמאות של אלג'יריה, ואל ה-FLN השלטת. סגן הנשיא, עלי בלחאדג', היה מטיף צעיר מאלג'יר אשר היה ידוע בנאומיו התוקפניים והרדיקליים, שנתמכו בידי הצעירים ואנשי המעמדות הנמוכים, והביאו לדאגה בקרב האחרים, בשל דחייתו את הדמוקרטיה, ודעותיו הקיצוניות באשר למעמד האישה. בלחאדג' היה בעל תפקיד חשוב במהומות אוקטובר. ה-FIS הפכה עד מהרה למפלגה האסלאמית הגדולה ביותר, וזכתה להצלחה ניכרת ביישובים העירוניים. בבחירות המוניציפליות שהתקיימו בשנת 1990 זכו לניצחון גדול, ול-54% מן הקולות. מלחמת המפרץ הראשונה, ב-1991, הביאה לתמיכה במפלגה, בשל התנגדותם הקולנית לקואליציה שקמה בהנהגת ארצות הברית כנגד סדאם חוסיין, בעוד שהממשלה נאלצה לנקוט עמדה מתונה יותר.
במאי 1991 ה-FIS קרא לשביתה כללית על מנת למחות כנגד עריכתם מחדש של אזורי הבחירה על ידי הממשלה, שנועדה להבטיח רוב למפלגות התומכות בממשלה. השביתה עצמה נכשלה, אך הפגנות ענק בעיר אלג'יר הרשימו את ההמונים, ולבסוף הפסיקה ה-FIS את השביתה לאחר שהובטחו לה בחירות הוגנות. בסמוך לאחר מכן עצרה הממשלה את מדאני ובלחאדג', ועמם מספר חברים בולטים נוספים במפלגה. המפלגה לא הוצאה מחוץ לחוק, והונהגה על ידי עבדאלקאדר חשאני.
עליית המפלגה המשיכה. לבסוף הסכימה להשתתף בבחירות, לאחר שפלטה מתוכה פעילים שהטיפו לפעולה אלימה כנגד הממשלה. בסוף נובמבר התקיפו קיצונים אסלאמים מזוינים עמדת גבול באזור גואמר, אך פרט לכך שרר שקט מתוח. ב-26 בדצמבר ה-FIS זכתה בבחירות לאספה הלאומית, כאשר קיבלה 48% מן הקולות, ו-188 מתוך 232 המושבים. ניצחון ה-FIS והקמת ממשלה אסלאמית נראו בלתי נמנעים.
הפיכה צבאית ותחילת הלוחמה המזוינת.
הצבא לא קיבל התפתחות זו. ה-FIS העלתה איומים בוטים כנגד אנשי הצבא, וכינתה אותם כבלתי פטריוטים ופרו צרפתים, וכן מושחתים. בנוסף לכך הנהגת ה-FIS לא תמכה בדמוקרטיה, ונראה כי ממשלתם תהפוך לדיקטטורה אסלאמית, או כלשונו של העוזר למזכיר המדינה האמריקני אדוארד ג'רג'יאן – "קול אחד לאיש אחד, פעם אחת".
ב-11 בינואר 1992 הצבא ביטל את הבחירות, והכריח את הנשיא בנג'דיד להתפטר, ולהעלות במקומו את לוחם העצמאות הגולה מוחמד בודיאף שישמש כנשיא. רבים מחברי ה-FIS נעצרו (המספר נע בין 5,000 על פי הצבא ובין 30,000 על פי נתוני ה-(FIS, וביניהם חשאני. הוקמו מחנות מעצר במדבר סהרה שכן מערכת בתי הכלא לא הייתה ערוכה לקלוט מספר כה רב של כלואים. מצב חירום הוכרז במדינה וזכויות האזרח הושעו. אנשים מזוקנים חששו לצאת מביתם על מנת שלא להיעצר כתומכי ה-FIS. ארגוני זכויות אדם כארגון אמנסטי הבינלאומי דיווחו על עינויים וכליאה ללא משפט. ב-4 במרץ הכריזה הממשלה על הוצאתה מחוץ לחוק של מפלגת ה-FIS ועל פיזורה.
בין המעטים ממנהיגי ה-FIS שנותרו בחופשי, ראו רבים את פעילות הממשלה כהכרזת מלחמה. הם התאחדו עם גורמים קיצוניים שנפלטו בעבר אל מחוץ למפלגה, והחלו בלוחמת גרילה בהרים. בתחילה התקיפו את כוחות הממשלה, ממעוזים בהרים בצפון המדינה, מקום בו פני השטח המיוערים מתאימים לסוג זה של לוחמה. ובערים מסוימות שאוכלוסייתן נטתה לתמוך באנשי האסלאם. מדבר הסהרה הבלתי מיושב נותר שקט כמעט במהלך כל המלחמה. מאחר ששדות הנפט, המהווים את עיקר הכנסת הממשלה האלג'ירית מצויים בסהרה, הבטיחה עובדה זו כי הממשלה לא תסבול מקשיי מימון במהלך הלחימה.
עם זאת, בתחילת הלחימה קרסה הכלכלה האלג'ירית. כל הסובסידיות על מזון בוטלו. התקוות שנתלו בדמותו של בודיאף קרסו עד מהרה כאשר זה נרצח בידי שומרי ראשו ביוני 1992. בסמוך לאחר מכן נדונו מדאני ובלחאדג' לשתים עשרה שנות מאסר.
ב-26 באוגוסט נראה ברור כי כמה מן הלוחמים שמים להם כמטרה פגיעה באוכלוסייה אזרחית. פיגוע בנמל התעופה באלג'יר גבה חייהם של תשעה בני אדם ופצע 128. ה-FIS גינה את הפיגוע, וכן עשו רוב המפלגות האחרות, אך בשלב זה השפעת מנהיגי ה-FIS על הלחימה הפכה להיות מוגבלת.
הלחימה, שהחלה כלחימה של קבוצות קיצוניות קטנות, המורכבות מבוגרי מלחמת אפגניסטן, הלכה והפכה לסכסוך כולל, עם התגבשות "התנועה האסלאמית המזוינת" – MIA, המונהגת בידי איש הצבא לשעבר עבדאלקאדר שבוטי. שבוטי הוא איש אסלאם קיצוני אשר התרחק ממנהיגי ה-FIS בשל התנגדותו להליכים פרלמנטריים. בפברואר 1992 ייסד סעיד מלחופי, קיצוני אסלאמי בוגר המלחמה באפגניסטן, את "התנועה למדינה אסלאמית" (MEI). קבוצות קיצוניות אלו ניסו לאחד את שורותיהן תחת הנהגתו של שבוטי. פגישה בין מספר מנהיגים על מנת לסכם את האיחוד בין הקבוצות הקיצוניות פוצצה על ידי כוחות המשטרה, והדבר העלה חשדות, ומנע איחוד בין הקיצונים האסלאמים המורדים.
ה-FIS הייתה בעלת רשת מחתרתית משלה, שכללה עיתונים מחתרתיים ותחנת רדיו, והחלה להנפיק הודעות "רשמיות" מחוץ לאלג'יריה. בשלב זה חלק מן הקיצונים התנגדו לפעילות ה-FIS.
בינואר 1993, עבדאלחאק לאיאדה, הכריז על עצמאות קבוצתו מן הקבוצות המונהגות על ידי שבוטי. הקבוצה החדשה נקראה "הקבוצה האסלאמית המזוינת" GIA (בצרפתית "Groupe Islamique Armé") והיא הפכה לפעילה באזורים העירוניים ובשכונות. הקבוצה נקטה בקו נוקשה, התנגדה לממשלה ול-FIS, ואיימה על מנהיגי ה-FIS וה-MIA. בניגוד ל-MIA אשר ביצע "סינון אידאולוגי" של הלוחמים, קיבלה ה-GIA לשורותיה את כל מי שחפץ בכך. כתוצאה מכך היו מקרים רבים של חדירת סוכנים של כוחות הביטחון, וראשי ה-GIA נהרגו בזה אחר זה.
החלוקה הפנימית בקרב לוחמי הגרילה הפכה למובהקת יותר בשנת 1993. ה-MIA וה-MEI ניסו לייצר אסטרטגיה שמטרתה לערער את המדינה, והתרכזו במאבק כנגד כוחות הביטחון, ובפעולות כנגד מוסדות המדינה. ה-GIA התרכז באזורים העירוניים והרג כל מי שנראה כתומך הממשלה, כגון עובדי הממשלה, מורים ואנשי מנהל. ה-GIA שם לו למטרה גם עיתונאים ואינטלקטואלים, ועד מהרה החל לבצע רציחות של כל מי שלא קיבל עליו את אורח החיים האסלאמי הנוקשה לו הטיף, ואף זרים. פעולות אלו הביאו להתרוקנותה של אלג'יריה מזרים, ולתנועה של הגירה מחוץ לאלג'יריה של אלג'יראים שקצו בלחימה ובטרור. במקביל לכך, החלו ממשלות מחוץ לאלג'יריה להוריד את מספר הויזות שניתנו לאזרחי אלג'יריה.
כישלון מאמצי המשא ומתן והלוחמה בין הקבוצות האסלאמיות.
האלימות המשיכה אף בשנת 1994 על אף השיפור במצב הכלכלי. כאשר נראה כי אין קץ נראה לעין ללחימה, הגנרל זרואל הוכרז כנשיא "המועצה העליונה של אלג'יריה". זרואל היה בין אנשי הצבא שתמכו בדיאלוג. לאחר שמונה למשרה, החל במשא ומתן עם אנשי ה-FIS הכלואים, ושיחרר רבים מהם כמחווה. השיחות פיצלו את הקשת הפוליטית. התנועות הפוליטיות העיקריות – ה-FLN הסוציאליסטית, ומפלגות סוציאליסטיות נוספות, קראו לפשרה, אך מפלגות שמאל אחרות, וכן ארגוני נשים, התנגדו לכל פשרה עם המוסלמים הקנאים. מיליציות שתמכו בממשלה החלו להתקיף את אנשי האסלאם בערים. ב-10 במרץ 1994 נמלטו אלף אסירים אסלאמיים מן הכלא, ונראה כי הקיצונים האסלאמיים זכו בניצחון גדול. יש המשערים כי בריחה זו נועדה להחדיר סוכנים של הממשלה להנהגת ה-GIA.
בינתיים, תחת הנהגתו של שריף גואוסמי, שקיבל לידיו את הנהגת ה-GIA במרץ 1994 הפכה ה-GIA לארגון העיקרי הלוחם בממשלה. במאי ספגה ה-FIS מהלומה, כאשר מנהיגיה שנותרו מחוץ לכלא, וכן אנשי ה-MEI הצטרפו אל ה-GIA, על אף שזה הוציא כנגדם איומי רצח מזה מספר חודשים. הדבר בא כהפתעה, ונראה כי יסודו ברצון אנשי ה-FIS לשנות את ה-GIA מתוך שורות הארגון. ב-26 באוגוסט הכריז ה-GIA על מדינה אסלאמית, או "ח'ליפות", בהנהגת ה"ח'ליפה" גואומי. הדבר הביא לפרישת אנשי ה-MEI מן ה-GIA. הארגון המשיך בהתקפותיו על מטרותיו הרגילות, ובשלב זה החל בהצתתם של בתי ספר שלא עמדו בתוכנית לימודים אסלאמית דיה לדעת אנשי הארגון.
הלוחמים הנשמעים ל-FIS היו עתה בשולי המאבק. הם ניסו לאחד את כוחותיהם עם אנשי ה-MEI, וביולי 1994 נוסד "צבא הישועה האסלאמי" המחודש והמאוחד (AIS). המסגרת החדשה איחדה לוחמים שהתנגדו הן לממשלה והן לקיצונים. ההתארגנות החדשה חיזקה את כוחו של ה-FIS במשא ומתן עם הממשלה. בסוף 1994 היו יותר ממחצית הלוחמים מאוחדים במסגרת זו במזרח ובמערב המדינה. אך במרכז המדינה, ליד הבירה אלג'יר, הייתה יד ה-GIA על העליונה, ואנשי ה-AIS היו אך כחמישית מן הלוחמים. אנשי החזית החדשה גינו את פגיעתם של אנשי ה-GIA בנשים, בעיתונאים ובאזרחים שאינם "מעורבים בדיכוי" והתקיפו את נטייתם של אנשי ה-GIA להצית בתי ספר.
בסוף אוקטובר הכריזה הממשלה על כישלון השיחות. זרואל יצא ביוזמה חדשה. הוא יזם בחירות לנשיאות אלג'יריה ב-1995, וקידם בשורות המפלגה קיצוניים המתנגדים לפשרה עם אנשי האסלאם, כמו גם תמך ב"מיליציות להגנה עצמית" שנלחמו בקיצונים האסלאמים באזורים הכפריים. סוף שנת 1994 הביאה להסלמה במאבק האלים. במהלך השנה העמיק בידודה של אלג'יריה. רוב סוכנויות הידיעות הזרות כבר לא החזיקו עיתונאים בארץ, והגבול עם מרוקו נסגר, כמו גם כל משרדי חברות התעופה הזרות. הממשלה הורתה לעיתונות שלא לדווח על ידיעות שלא הופצו באמצעות סוכנות הידיעות הרשמית. הדבר הביא לפער של ממש בין המתרחש בשטח לבין המידע שהיה לגורמי חוץ ואף לאזרחי אלג'יריה על הנעשה.