יש מידע מועט בלבד על יהודים באזור אלג'יריה בתקופה שבין הכיבוש המוסלמי למאה ה-12. ישנם כמה תשובות של הגאונים שמוכיחות שבתקופה זו רבנים יהודים מהעיר תלמסאן התכתבו עם הגאונים בישיבות בבל וניהלו קשרי מסחר עם מצרים. על פי ממצאי הגניזה הקהירית ידוע שבעיר תיארת שבמרכז אלג'יריה ישבו מספר מלומדים וסוחרים יהודים חשובים, וממנה יצאו סוחרים למקומות מרוחקים עד הודו. לאחר כיבושה והריסתה החלקית של תיארת על ידי שבטי בנו הלאל בתחילת המאה ה-10 מתמעטות הידיעות על יהודים בעיר.
בתקופת השושלת בני חמאד (1014–1152) נהנו כנראה היהודים באזור אלג'יריה משקט וביטחון יחסיים. בתקופה זאת הוקמה קלעת בני חמאד שהייתה עיר הבירה של השושלת עד 1090. מספר מלומדים יהודים נולדו או פעלו בעיר - הגדול שבהם הוא הרי"ף, רבי יצחק אלפאסי, שנולד בקלעת בני חמאד ובהמשך היגר ממנה לפאס ואחר כך לספרד. ר' יצחק אלפאסי הוא מגדולי הראשונים ומי שספרו הלכות רב אלפס מהווה ספר יסוד בהלכה היהודית. בנוסף פעלו בעיר או נולדו בה בתקופה זאת רבנו אפרים, המילונאי ר' שלמה אבן פרחון, והרופא ר' שלמה הדיין בן פורמש. בשנת 1090, בעקבות התקפות חוזרות ונשנות של השושלת הפאטמית ממזרח על קלעת בני חמאד, הקימה השושלת החמאדית עיר בירה חדשה בשם בג'איה, והזמינה אליה תושבים חדשים תוך הבטחה לפטור ממיסים. כך קם גם בעיר זאת מרכז יהודי חשוב.
ימי הביניים המאוחרים.
יהדות אלג'יריה הייתה בין הקהילות שסבלו קשות מרדיפות אל-מוואחידון במאה ה-12, שכללו בשלב מסוים גזירה על היהודים לבחור בין התאסלמות, גירוש או מוות. בתקופה זאת נהרגו המוני יהודים על קידוש השם, רבים אחרים היגרו, ואלה שנשארו נאלצו לחיות כאנוסים ולשמור על יהדותם בסתר. מקורות מהתקופה מציינים שלא התקיימו חיים יהודיים גלויים בתקופה זאת במגרב, כולל ערי אלג'יריה. מספר קינות לזכר הקהילות היהודיות שחרבו כתוצאה מהרדיפות מאזכרות גם את קהילות אלג'יריה השונות. כך למשל בקינה המפורסמת שחיבר ר' אברהם אבן עזרא על המאורעות, אהה ירד עלי ספרד, הוא כותב על קהילת תלמסאן מצפון-מערב אלג'יריה:
בהשלמות לאותה קינה שחיברו משוררים אחרים הם הזכירו גם קהילות אלג'יראיות נוספות שחרבו, כגון בג'איה:
קלעת בני חמאד נהרסה כליל על ידי שושלת אל-מוואחידון ונותרו ממנה רק שרידים, וכך בא לתומו גם המרכז היהודי בעיר זאת.
לאחר התפוררות שושלת אל-מוואחידון הוקמה על מרבית שטח אלג'יריה של ימינו ממלכת תלמסאן על ידי השושלת הזיאנית (1235-1534). יחסם של שליטי שושלת זו ליהודים היה סובלני יחסית, ושרידי הקהילות היהודיות בערי אלג'יריה החלו אט-אט להשתקם באמצעות זרם מהגרים איטי מספרד. לאורך ימי הביניים הייתה תנועה תמידית דו-סטרית של יהודים בין צפון אפריקה לספרד, אך בעקבות התקדמות הרקונקיסטה הפכה התנועה להיות בעיקר חד סטרית - של פליטים יהודים מספרד לצפון אפריקה. כך למשל, בין המהגרים המפורסמים המוקדמים מספרד לצפון אפריקה היה הרופא ר' שמואל אשתרוק הכהן שהגיע במחצית השנייה של המאה ה-14 לעיר תלמסאן, עיר הבירה של הזיאנים, והפך לראש הקהילה היהודית בעיר. אולם גל המהגרים היהודים הגדול ביותר מספרד הגיע לאלג'יריה בשנת 1391 עקב גזירות קנ"א. כתוצאה מהגזרות המוני פליטים יהודים מספרד הגיעו לחופי אלג'יריה בספינות. כרוניקאי מוסלמי אחד מספר שמספר הספינות שהתקרבו לנמל אלג'יר היה כה גדול שהמוסלמים המקומיים חשבו שזה צי צבאי שמתקרב והטביעו חלק מהספינות, אך לבסוף וזיר (שר) יהודי מקומי הצליח לשכנע את השליט המוסלמי לאפשר לספינות להיכנס לנמל.
גל פליטי גזירות קנ"א היווה נקודת ציון משמעותית בתולדות יהודי אלג'יריה, וכתוצאה ממנו ערי הנמל של אלג'יריה הפכו למרכזים חשובים של מחשבה יהודית. בין הפליטים שהגיעו לאלג'יריה היו מלומדים גדולים מספרד אשר הגדולים והמפורסמים שבהם היו ר' שמעון בן צמח דוראן (הרשב"ץ), ר' יצחק בן ר' ששת (הריב"ש) ור' אפרים אנקווה. הראשון שבהם התפרסם גם בזכות עיסוקו ברפואה ופילוסופיה, ובנו ר' שלמה בן שמעון דוראן (הרשב"ש) נחשב גם כן לאחד מגדולי חכמי אלג'יריה. בעקבות בואם של מלומדים אלה לעיר אלג'יר, היא זכתה למעמד בכורה בתקופה זאת בקרב הקהילות היהודיות בצפון אפריקה וספרד. דמות חשובה נוספת שהגיעה לאלג'יריה עם פליטי קנ"א הוא הרופא ר' שמואל אלאשקר, שהתיישב בתלמסאן והפך לרופא הבכיר בעיר ולמקורב לשליט המוסלמי.
בשנת 1492 הגיע לאלג'יריה גל פליטים יהודים נוסף, מצומצם יותר, כתוצאה מגירוש ספרד. רק מספר קטן מהמגורשים של שנת 1492 בחרו להתיישב באלג'יריה, כנראה עקב החשש שספרד תכבוש את ערי אלג'יריה והם יסבלו מידה גם משם.
במחצית השנייה של המאה ה-15 פעל באזור תלמסאן ובקהילות הדרומיות של אלג'יריה באזור הסהרה מטיף מוסלמי קנאי בשם מוחמד אל-מגילי (בערבית: محمد المغيلي) אשר הסית את האוכלוסייה המוסלמית כנגד היהודים, והביא לחיסולן של קהילות שלמות באזור הדרומי של אלג'יריה.
בתחום הכלכלה, היהודים באלג'יריה שלאחר ימי אל-מוואחידון שיחקו ברציפות תפקיד חשוב בסחר בין צפון אפריקה לספרד, ובסחר הבינלאומי של ערי הנמל אלג'יריה ככלל, ויהודים התבלטו במיוחד בסחר בזהב. כדי להקל על המסחר לעיתים משפחות מורחבות התפצלו כך שחלקם חיו בספרד או מיורקה וחלקם בערי אלג'יריה. יהודים בודדים כגון אברהם אבנגלל (סוף המאה ה-13) אף שימשו כשגריריהן של הממלכות הנוצריות בערי אלג'יר. חלק נוסף מהיהודים עסק במסחר מקומי, ורבים מצאו פרנסה ברכישה של סחורה במחיר זול בעיר אחת באמצעות הלוואה ונדודים לעיר אחרת שבה ניתן למכור אותה במחיר גבוה יותר. מקצועות יהודים נוספים היו מלאכות יד כגון צורפות, ניקוב אלמוגים, ייצור אלכוהול, תיווך, ועוד.
התקופה העות'מאנית וכיבושי ספרד.
מראשית המאה ה-16 עד שנת 1830 רוב חלקי אלג'יריה של ימינו היו חלק מהאימפריה העות'מאנית ובשליטתו של שליט מקומי ("דאי") מטעמה. חלקיה הדרומיים של אלג'יריה היו לרוב בשליטת גורמים מקומיים, בעוד שאוראן בצפון-מזרח אלג'יריה נותרה בשלטון ספרדי. התקופה העות'מאנית באלג'יריה הייתה רוויית מאורעות קשים עבור היהודים, והיהודים זכו באלג'יריה בדרך כלל לפחות ביטחון והגנה מאשר בחלקים אחרים של האימפריה העות'מאנית.
ישנם תיאורים רבים של כותבים יהודים או אירופאים המתארים את מעמדם המושפל של היהודים ואת ההתאכזרויות התדירות כלפיהם. באמצע המאה ה-16 היהודים בעיר אלג'יר הואשמו שהם אחראים לתסיסה נגד השלטון העות'מאני. מקור יהודי מהתקופה מתאר שהשליט העות'מאני המקומי (דאי) כעס "ורצה לאבד את כל היהודים", אך "תפילות ורחמים מן השמים" גרמו לכך שהוא הסתפק בהטלת עבודות פרך יומיות על היהודים וחייב אותם לשכן את החיילים העות'מאנים בבתיהם (דבר שהרע את מעמדם של היהודים מבחינות רבות). לקראת סוף המאה ה-17 ר' שלמה בן צמח דוראן כתב שרציחות נגד יהודים הם דבר תדיר שעובר ללא כל ענישה, והרוצחים מסתובבים בחופשי ומתרברבים על מעשיהם. בשנת 1794 הוצא להורג ר' מרדכי נרבוני באלג'יר, רב מקומי של הקהילה, באשמת חילול האסלאם.
בראשית המאה ה-16 ספרד וצרפת החלו לפלוש לערי הנמל של אלג'יריה, והיהודים סבלו רבות מכך. החל משנת 1509 העיר אוראן וסביבתה, היו תחת שליטתה של האימפריה הספרדית למשך מרבית 300 השנים הבאות. במסגרת כיבוש אוראן על ידי ספרד נהפך בית הכנסת בעיר לכנסייה ונערכו מעשי פרעות ואונס מצד הצבא הספרדי ביהודים, מה שהוביל לנטישת העיר בידי יהודים רבים. עם זאת, המשיכה להתקיים באוראן קהילה יהודית קטה אף תחת השלטון הספרדי, זאת על אף שבתקופה זאת יהודים לא הורשו להתגורר בשטח ספרד ומושבותיה. משפחות יהודיות מסוימות באוראן אף שירתו את המלך הספרדי בתחומי הכלכלה והדיפלומטיה. בשנת 1541 ספרד בראשות קרל החמישי (שנודע באיבתו ליהודים) ניסתה לכבוש גם את העיר אלג'יר והיהודים חששו מהגורל המצפה להם, אך שרשרת של תאונות ופגעי טבע גרמה לצבא הספרדי לנסוג מובס. מספר פיוטים נכתבו על ידי משוררים יהודים מאלג'יר לכבוד הנס והיום ד' בחשוון נקבע כ"פורים שני" ויום טוב בקרב יהודי אלג'יריה לדורות. עם זאת, עד מהרה ספרד שבה ופלשה לאלג'יריה, וכבשה בשנת 1543 את העיר תלמסאן. כ-1,500 יהודים נשבו, חלקם נמכרו לעבדות או אולצו להמיר את דתם לנצרות, יהודים אחרים בני העיר נמלטו והרחיקו עד פאס במרוקו כדי לבקש מהקהילה היהודית בה סיוע לפדיון שבויים. בניגוד לאוראן שנותרה תחת שלטון ספרדי עוד זמן רב, תלמסאן חזרה במהרה לשלטון עות'מאני.
במהלך המאה ה-17 הגיעו לערי צפון אלג'יריה מהגרים יהודים מליבורנו, איטליה. מהגרים אלה היו צאצאיהם של מגורשי ספרד והם התיישבו בצפון אפריקה בתור סוחרים ובחיפוש אחר הזדמנויות כלכליות, ועד מהרה נהפכו לגורם משמעותי בסחר הבינלאומי של ערי אלג'יריה. הם סיפקו שירותים פיננסיים ומסחריים חשובים לדאי (השליט המקומי) וכמה מהם מונו לאורך השנים לכהן בתפקיד ה"מוקדם", המתווך בין הקהילה היהודית לשלטון. שתיים מהמשפחות הבכירות מקרב יוצאי ליבורנו באלג'יריה היו משפחת בכרי ומשפחת בוג'נאח. שתי משפחות אלה חברו בסוף המאה ה-18 והקימו חברה כלכלית שהייתה דומיננטית ביצוא של מזון מאלג'יריה לצרפת, בין השאר כדי לספק את צרכיו של צבא נפוליאון. צרפת צברה חובות של 14 מיליון פרנק לחברת בונג'אח-בכרי בלי היכולת לשלם אותם, והדבר יצר מתיחות רבה ביחסי צרפת-אלג'יריה (ראו עוד: פרשת בוג'נאח-בכרי). מתיחות זאת הייתה בין הגורמים לפלישת צרפת לאלג'יריה ב-1830.