Insgesamt 44 Mannschaften meldeten sich zur Teilnahme am Afrika-Cup 1996, die ursprünglich in Kenia stattfinden sollte. Titelverteidiger Nigeria und der ursprünglich vorgesehene Gastgeber Kenia waren automatisch für die Endrunde gesetzt. Die 42 übrigen Mannschaften wurden in sieben Sechsergruppen eingeteilt. Die sieben Gruppensieger und sieben Gruppenzweiten qualifizierten sich für das Endrundenturnier, dessen Teilnehmerfeld von 8 auf 16 Mannschaften erweitert wurde.
Kenia verzichtete jedoch auf die Ausrichtung des Endrunden-Turniers und wurde deswegen vom Afrikanischen Fußballverband (CAF) von der Qualifikation ausgeschlossen; und durfte auch nicht am Endrundenturnier teilnehmen. Zum Ersatzausrichter des Endrundenturnieres wurde Südafrika bestimmt. Damit war Südafrika auch automatisch für die Endrunde gesetzt. Die bereits von Südafrika ausgetragenen Qualifikationsspiele wurden aus der Wertung genommen.
Überdies zogen sich im Laufe der Qualifikation elf Mannschaften zurück und Titelverteidiger Nigeria trat zur Endrunde in Südafrika nicht an. Guinea wurde angeboten für Nigeria einzuspringen, aber Guinea verzichtete ebenfalls. Die Endrunde wurde daraufhin nur mit 15 Mannschaften ausgetragen.