من البرتغال إنطلقت فكرة إقامة بطولة إفريقية تجمع بين منتخبات القارة، حينما إجتمع مسؤولو الاتحاد الدولي لكرة القدم واقترح خلال مجموعة من المسؤولين الأفارقة إقامة البطولة، لتبدأ القارة السمراء في تقديم عرسها الإفريقي عام 1957. ففي الثامن من يونيو 1956 اجتمع المصريان عبد العزيز سالم ومحمد لطيف والسودانيون عبد الحليم شداد وبدوي محمد وعبد الحليم محمد والجنوب إفريقي فرد ويل في فندق "أفينيدا" البرتغالي مع مسؤولي الفيفا ليناقشوا فكرة تأسيس الاتحاد الإفريقي وإطلاق مسابقة بين منتخباته. وبعد ثمانية أشهر بالفعل انطلقت النسخة الأولى من بطولة كأس الأمم الإفريقية رسمياً في العاشر من فبراير 1957 على الملعب البلدي في الخرطوم. كانت النسخة الأولى من البطولة محدودة، إذ شاركت فيها ثلاث دول هم مصر وأثيوبيا إضافة إلى السودان البلد المضيف، وكان من المفترض أن تشارك جنوب إفريقيا ليصل عدد الفرق المشاركة إلى أربعة منتخبات، إلا أن سياسة الفصل العنصري حرمتها من الاشتراك على مدار 39 عاماً. وشهدت العاصمة السودانية المباراة الأولى في تاريخ البطولة، بين الفراعنة والبلد المضيف، والتي فازت فيها مصر، بعد أن أحرز رأفت عطية أول أهداف البطولة من ركلة جزاء في الدقيقة 21، ليتعادل بعدها صديق منزول لأصحاب الأرض في الدقيقة 58، قبل أن يحسم المصري محمد دياب العطار الشهير ب"الديبة" المواجهة بهدف في الدقيقة 72، لتنتهي المباراة بفوز مصري. ثم التقت مصر مع إثيوبيا في النهائي، ليسحق الفراعنة منافسيهم برباعية نظيفة أحرزها "الديبه" ليصبح الهداف الأول للبطولة برصيد خمسة أهداف. وعادت الدول الثلاثة للمنافسة على اللقب الثاني للبطولة عام 1959، بعدما شهدت أول تغيراتها، لتتنافس مصر المضيفة والسودان وإثيوبيا في دوري من دور واحد. كانت البطولة الثانية متشابهة إلى حد كبير مع سابقتها، لتكرر مصر فوزها الثقيل على إثيوبيا في الافتتاح بأربعة أهداف، وتفوز في النهائي على السودان بهدفين مقابل هدف، بعدما تقدم عصام بهيج للفراعنة، ثم تعادل منزول للسودان، وأضاف بهيج هدف الفوز قبل نهاية الوقت الأصلي للمباراة بدقيقة واحدة، لتحتفظ مصر باللقب ليعلن تتويج الفراعنة بثاني ألقابهم الإفريقية والذي سيعجزون عن انتزاعه مجددا لمدة 27 عاماً. مشاركة تونسية ظهر نظام التصفيات للمرة الأولى في النسخة الثالثة من البطولة التي استضافتها إثيوبيا عام 1962، ما نتج عنه استبعاد نيجيريا وغانا والمغرب وكينيا والسودان، لتشارك تونس وأوغندا في النهائيات مع البلد المضيف ومصر حامل اللقب.
جمهور جنوب إفريقيا حُرم من البطولة 39 عاما وخلال البطولة التي أقيمت بنظام خروج المغلوب، فازت إثيوبيا على تونس بأربعة أهداف مقابل هدفين، وتغلبت مصر على أوغندا بهدفين مقابل هدف، وسجل هدفي الفراعنة صالح سليم وبدوي عبد الفتاح. وعادت مصر والتقت بأثيوبيا في النهائي، ولكن الرباعية هذه المرة كانت من نصيب البلد المضيف، فبعد التعادل 2-2 خلال الوقت الأصلي للمباراة، استطاع أصحاب الأرض تسجيل هدفين في الوقت الإضافي ليفوزوا باللقاء والكأس للمرة الأولى. وشهدت النسخة الرابعة عام 1963 ظهور عمالقة غرب القارة، بعد وصول نيجيريا وغانا – الدولة المضيفة – للنهائيات، كما استمرت التغييرات في نظام البطولة، لتقام هذه المرة بنظام المجموعات، بدون إقامة الدور قبل النهائي، ليلعب بطلا المجموعتين في المباراة النهائية مباشرة. وتربع أصحاب الأرض على قمة المجموعة الأولى، بعد الفوز على إثيوبيا والتعادل مع تونس، في حين كانت الإثارة من نصيب المجموعة الثانية، التي تغلبت فيها مصر على نيجيريا 6-3، ثم تعادلت مع السودان بهدفين لكل منهما. ولكن فوز السودان على نيجيريا بأربعة أهداف نظيفة، وضعهم على القمة بفارق هدف وحيد عن الفراعنة. غياب مصري وفي النهائيات فازت مصر على إثيوبيا بثلاثة أهداف في مباراة تحديد المركزين الثالث والرابع، وهي النتيجة ذاتها التي انتهت إليها مباراة غانا والسودان لتتوج النجوم السوداء أبطالاً لإفريقيا للمرة الأولى، في حين عاد المصري حسن الشاذلي بكأس هداف البطولة. وفي تونس عام 1965 غابت مصر للمرة الأولى، في حين ظهرت عيوب نظام المجموعات مع انطلاق مباريات النسخة الخامسة من البطولة. ففي المجموعة الأولى لجأت اللجنة المنظمة للقرعة لتحديد بطل المجموعة، بعد تعادل البلد المضيف مع السنغال في النقاط وفارق الأهداف. وفي المجوعة الثانية اجتاحت غانا كل من الكونجو بخمسة أهداف مقابل هدفين، وكوت ديفوار بأربعة أهداف مقابل هدف، لتصعد إلى النهائي وتقابل تونس. وفي نهائي النسخة الخامسة من ا