בתקופה שבה האימפריה הביזנטית שלטה בצפון אפריקה, לפעמים קיסרים גזרו גזרות שונות על יהודי האזור, על אף שלא ברור עד כמה הן נאכפו על ידם. כך למשל הקיסר יוסטיניאנוס הראשון במאה ה-6 הוציא צו נגד היהודים ועמים לא-נוצרים אחרים בצפון אפריקה שהגביל את הפולחן הדתי שלהם, הורה על הפיכת בתי כנסת לכנסיות, והביע תקווה שהם יאמצו את דת הנצרות, עם זאת ההוראות של הצו כנראה לא נאכפו בפועל. ישנן עדויות שגם בתקופת שלטונו של הקיסר הרקליוס (610-641) היו רדיפות על רקע דתי כנגד היהודים בצפון אפריקה. בספר דוקטרינת יעקב מהמאה ה-7, חיבור פולמוסי כנגד היהדות, כתוב שהיהודים בצפון אפריקה אולצו להיטבל לנצרות. אולם יש מחלוקת בין חוקרים של התקופה לגבי טיבן ואמינותן של עדויות אלה.
תהליכי גיור בעת העתיקה.
תהליכי גיור במרחב הים התיכון.
בתקופה שבין מרד המכבים במאה ה-2 לפנה"ס לבין מרד בר כוכבא במאה ה-2 לספירה, עלה שיעור המאמינים היהודים בעולם התרבות הים תיכונית, לשיא שלא יחזור על עצמו אלא בראשית העת המודרנית. למרות הניגוד העצום בין היהודים ואומות העולם, ניכרת נטייה לדת היהודית, בקרב הקהל האלילי. היוונים והרומים המשכילים, שהכירו את דעות היהדות מתוך התרגום היווני של התורה ומתוך הספרות היהודית ביוונית, נמשכו לפעמים אחרי המושגים הנעלים של אלוהים, מוסר ותכלית החיים שבספרות זו. תורת האל המופשט, בורא העולם ומקור האמת העליונה כאחד ואחדות האל. דבקותם של היהודים באמונתם, קידוש השבת לצורכי הנפש העליונים, טהרת המשפחה, מסירת נפשם על אמונתם – כל אלה עוררו כבוד ליהדות. בנוסף, עיקר גדול הייתה ההטפה של היהדות. יהודי הגולה היו נאלצים לעיתים מזומנות להוכיח לנוכרים את צדקת דת ישראל, ומתוך כך באו לידי הוכחת הטעות שבדעות מתנגדיהם. כך הלכו והתפשטו האמונות והדעות היהודיות בין המוני עובדי האלילים שבארצות הגולה.
הקשרים בין היהודים לתושבים הפיניקיים והברברים.
ההשפעה השמית החלה להסתמן בצפון אפריקה, עם תחילת ההתיישבות הפיניקית, בתחילת המאה השמינית לפנה"ס. המתיישבים היהודים הראשונים, שעזבו את ארץ ישראל, בטרם תירש שם הארמית את העברית, התיישבו בסביבה פונית ודיברו בשפתם המקורית שהייתה מובנת לאחיהם-שכניהם החדשים. יחסי השכנות התהדקו בזכות השיתוף בלשון, שהכשירה את הקרקע להשתלבות עמוקה בין היהודים לפונים והברברים שבמגרב. אחרי כישלון מרד הגלויות והטבח ביהודים, התרחקו היהודים הפזורים ביבשת אפריקה, מן העולם הרומי, והתקרבו אל הברברים. סכסוך נוסף היה המאבק המתמיד של המתיישבים נגד הנוודים. בתקופת בית סוורוס (הקיסרים ספטימיוס סוורוס ובנו מרקוס אורליוס אנטונינוס), הדפה ההתנחלות הרומית את הנוודים הברברים אל המדבר, ואת שטחי המרעה שלהם החרימה לטובת המתנחלים. ההיסטוריון אבן ח'לדון, חילק את הברברים לשני ענפים עיקריים: הבותר (נוודים) והבראנס (תושבים).
השפעות יהודיות ותהליכי התגיירות.
פעולת הגיור היהודית, זכתה להצלחה בעיקר בקרב שבטי הבותר. לפי אבן ח'לדון, היו יהודים בקרב הברברים של טמינה ותדלה. גם בתואת, מספרים היסטוריונים ערביים על קיומם של יהודים ברברים בני שבט זינאתה. גם באזורים מרוחקים של המגרב, נמצאו יהודים בשבט בני-מדיונה. אבן ח'לדון מזכיר שבטים ברברים נוספים שהחזיקו ביהדות: בני-ג'ראווה, שבטי נפוסה, בני פנדלאוה, בני בהלולה, בני גראתה ובני פזאן. ליהודי צפון אפריקה הייתה השפעה עמוקה גם על יושבי קבע, שמקובל היה אצלם מין סינקרטיזם יהודי-פוני. האבלונים והקליקולים, היו כיתות שכללו יהודים שהתנגדו לאדיקות נוסח ארץ-ישראל וגם פגנים מתייהדים. יהודים-פוניים אלה, שידעו את התנ"ך, היו מָלים את ילדיהם, ומקומם היה "על הגבולות המטושטשים שבין היהדות, הנצרות והעכו"מיות השמית". הנוצרים והרומים ראו בהם יהודים, ובשם זה התקראו גם הם עצמם, על אף שלא היו אדוקים בדתם. נטייה זו לסינקרטיזם, הופיעה כאחד מגורמי-הקבע בהיסטוריה היהודית בצפון-אפריקה. מהמאה השלישית עד למאה השביעית, יש מכלול של עדויות להשפעתה של היהדות בצפון-אפריקה. עובדה ראויה לציון: ההשפעה היהודית לא נשענה על כוח חילוני. הנצרות, החל מימי קונסטאנטינוס, והאסלאם אחריה, היו עטורים ביוקרה של השלטון, ונשענו על אמצעי הלחץ של השלטון. היהדות, כנגד זאת, לא היה לה שום אמצעי אחר מחוץ לכלי הבלתי-גשמי, של ההטפה. הברברים, שכבר נעשו שמיים במידה רבה, לאחר דורות של השפעות קרתאגניות, נוטים היו לעזוב את פסיליהם ולהתווסף לאוהדי ונאמני בית-הכנסת. טרטוליאנוס מספר במאה השלישית לספירה, איך היו הברברים שומרים את השבת, את ימי החג והצום, ואת דיני הכשרות. במאות הבאות, תחת שלטון רומא הנוצרית ולאחר מכן השלטון הביזנטי, היהודים נדחקו בהדרגה מהחיים האזרחיים והוטלו עליהם מגבלות קשות. ההטפה הנוצרית זכתה להצלחה בקרב המוני הברברים ורבים מהם התנצרו, עד לכיבוש המגרב על ידי חסן אבן אל-נעמאן אל-גסאני, מושלה של מצרים. הכובש ניהל מלחמת מצווה (ג'יהאד), ותוך זמן קצר התרחשה המרה המונית של מרבית שבטי הברברים, לדת האסלאם.
בימי הביניים.
במהלך המאה ה-7 נכבשה תוניסיה על ידי הצבא המוסלמי בראשות הגנרל עוקבה בן נאפע. ישנן מסורות לגבי מנהיגה ברברית בשם קהינה שאיחדה את השבטים הברברים והובילה אותם במאמצם להדוף את הכיבוש המוסלמי של צפון אפריקה. על פי חלק מהמסורות קהינה אף הייתה יהודייה או משבט ברברי שהתייהד, אך מקובל כיום לפסול השערות מעין אלה. השאלה האם אל-קהינה הייתה אישיות היסטורית או דמות בדיונית נתונה למחלוקת בין החוקרים.
כמו שאר הטריטוריות שנכנסו תחת שליטת האסלאם, היהודים באזור תוניסיה הוגדרו כד'ימים ונאכפו עליהם המגבלות של חוקי עומר. לפיכך הובטח להם ביטחון אישי והגנה על רכושם אם לא יחרגו מהמעמד הנחות שמוקצה להם על פי חוקים אלו. מידת אכיפת חוקי עומר השתנתה בין שליט לשליט והיו כאלה שהקלו עם היהודים בעוד שהיו כאלה שרדפו אותם.
עם כיבוש תוניסיה, עוקבה בן נאפע הקים את העיר קירואן, שנחשבה למרכז רוחני של עולם האסלאם. עד מהרה הפכה העיר גם לאחד המרכזים הרוחניים, תרבותיים, וכלכליים של העולם היהודי. במסמכי גניזת קהיר נמצא מידע רב על הקהילה היהודית של העיר. מהגניזה וממקורות נוספים ניתן ללמוד על פריחה כלכלית ותרבותית של היהודים בקירואן ובערים המרכזיות האחרות שבאזור תוניסיה של היום מסוף המאה ה-8 ועד לתחילת המאה ה-11. מעמדם של הסוחרים היהודים בקירואן היה גבוה במיוחד והם היו מהסוחרים הבולטים ברשתות המסחר הים-תיכוניות. בעיר פעלה ישיבה מפוארת, ובין המלומדים היהודים הגדולים שעמדו בראשה או למדו בה נכללים רב נסים גאון, רבי חושיאל בן אלחנן, חננאל בן חושיאל והרי"ף (רבי יצחק אלפסי). מלומדים יהודים מקירואן עלו למעמד רם גם בזכות מומחיות ברפואה. יהודי בשם יצחק בן שלמה הישראלי שימש כרופאם האישי של שליט השושלת האע'לבית האחרון ושל שליט השושלת הפאטמית הראשון, והוא עמד בקשר עם הרב סעדיה גאון בתחילת המאה ה-10. הוא חיבר מספר מאמרים על רפואה שתורגמו לאחר מכן לשפות נוספות. עוד נודע שמו של דונאש בן תמים, רופא ופילולוג בן העיר, ששימש גם הוא כרופא בחצר הפאטמית והיה פילוסוף שחיבר מאמר פרשנות לספר היצירה.
יהדות תוניסיה לקחה חלק בפעילות מסחרית רחבת היקף בין הלבנט, מצרים המגרב וספרד, כפי שניתן ללמוד מתעודות רבות שהתגלו בגניזת קהיר. לאזור תוניסיה הגיעו עד סוף המאה ה-11 מהגרים יהודים רבים מאזור הלבנט, והדבר תרם גם הוא לבניית הקשרים הכלכליים והאינטלקטואליים בין הקהילות היהודיות באגן הים התיכון. יהודים בתוניסיה היו דומיננטיים בתחום הצורפות והמסחר ועסקו גם במגוון מלאכות יד.
בין השנים 952–1022 חי בעיר תוניס חכם הלכה מוסלמי בשם סידי מחרז. על פי המסורת, חכם הלכה זה הוא שהתיר ליהודים להתיישב בין חומותיה של העיר תוניס, בנימוקים של טובת העיר והרחבת המסחר. אבן הפינה לבית הכנסת העתיק בעיר הונחה בנקודה שאליה השליך סידי מחרז את מקלו מן הצריח של המסגד הראשי. כך כנראה נוסדה השכונה היהודית (חארת אל-יהוד) בתוך חומות העיר תוניס. עד אז, היהודים אשר באו לסחור בעיר היו מחויבים לישון אך ורק ב"פונדוק" שהיה מיועד להם. וכל מי שלא מצא מקום בפונדוק נאלץ ללון בכפר קטן מחוץ לחומות העיר, שהוא כפר "מלאסין", השוכן כקילומטר מחומת העיר תוניס. הכפר מכונה עד היום "בלאד אל-יהוד" על אף שמזה שנים רבות אין גרים שם יהודים. היהודים שהגיעו לגור בעיר תוניס ב"חרת אל-יהוד" היו סוחרים ומהגרים שהגיעו מהעיר קורואן לאחר חורבנה על ידי שבטים בדואיים. לימים בעיר תוניס צמחה הקהילה הגדולה ביותר של יהודים בתוניסיה.
היהודים סבלו מירידות ועליות במעמדם הפוליטי בתוניסיה לאורך ימי הביניים. במהלך התקופה הפאטמית בדרך כלל לא ננקטו הגבלות או רדיפות קשות כנגד יהודים. מאידך לאחר שהזירים (زيريون) מרדו בפאטמים והחלו לשלוט באופן עצמאי על תוניסיה החלה תקופה קשה יותר עבור היהודים. בתגובה למרידה של הזיריים, השושלת הפאטמית שילחה בהם את שבטי בנו הלאל הבדואים, ואלה גרמו נזק רב לערים רבות ברחבי תוניסיה ובמיוחד לקירואן, אותה הם כבשו והרסו בשנת 1057. במהלך תקופה זאת התהפך זרם ההגירה ויהודים החלו להגר אל מחוץ לתוניסיה.