ג'יבוטי וקומורו פרשו לפני הגרלת המשחקים, ו-51 הנבחרות הנותרות התמודדו על 5 מקומות במונדיאל.
טורניר המוקדמות באפריקה הורכב משני סבבים. 9 נבחרות העפילו ישירות לסיבוב השני: 5 הנבחרות שהשתתפו במונדיאל 2002 (קמרון, ניגריה, סנגל, דרום אפריקה ותוניסיה) ו-4 הנבחרות הבכירות מלבדן לפי הדירוג העולמי של פיפ"א באותה עת (הרפובליקה הדמוקרטית של קונגו, חוף השנהב, מצרים ומרוקו. 42 הנבחרות האחרות חולקו לזוגות, ושיחקו אחת נגד השנייה בשיטת בית-חוץ, למעט בורקינה פאסו שהעפילה אוטומטית לסיבוב השני בגלל פרישת הרפובליקה המרכז אפריקאית. בסיבוב השני חולקו 30 הנבחרות ל-5 בתים בני 6 נבחרות כל אחד. הנבחרות שיחקו אחת נגד השנייה בשיטת בית-חוץ. הנבחרת הראשונה בכל בית העפילה למונדיאל.
טורניר מוקדמות המונדיאל באפריקה שימש גם כמוקדמות גביע אפריקה לאומות 2006, כאשר 3 הנבחרות הראשונות בכל בית העפילו לאליפות. החריגה היחידה מכלל זה הייתה במקרה של מצרים, שהעפילה אוטומטית כמארחת והוחלפה על ידי הנבחרת הרביעית בבית שלה. בסיום טורניר המוקדמות התברר כי 4 מתוך 5 הנבחרות (אנגולה, טוגו, חוף השנהב וגאנה) העפילו לראשונה בתולדותיהן, ורק לתוניסיה הייתה יותר מהופעה אחת במונדיאל.