Née d'un père célèbre journaliste malien, Mohamed Maïga, décédé en décembre 1987 à Ouagadougou dans des circonstances troubles, et d'une mère sénégalaise et gambienne, Aïssa Maïga passe les quatre premières années de sa vie à Dakar avant de s'installer à Paris. Elle fréquente le lycée Voltaire, dans le {{11e}} arrondissement.
Initiée au théâtre par son professeur de français de classe de sixième, enseignante originale et charismatique, et par sa tante qui le pratique en amatrice, Aïssa devient comédienne. Elle est formée au Laboratoire de l'acteur-Hélène Zidi par Hélène Zidi. Elle joue ensuite dans une comédie musicale, La Nuit la plus longue, pendant chaque été durant trois années consécutives. Aïssa obtient son premier rôle dans un court métrage, Le Royaume du passage. Son premier long métrage au cinéma se fait aux côtés d'Yvan Attal et Richard Bohringer dans Saraka Bô, film qui raconte une enquête policière sur un meurtre commis dans une communauté africaine.
Elle devient une actrice remarquée du cinéma français, rencontrant des réalisateurs prestigieux comme Michael Haneke (Caché) ou Claude Berri (L'un reste, l'autre part) mais elle se fait vraiment connaître grâce à son rôle dans Les Poupées russes (2004), dans lequel elle joue la petite amie de Romain Duris.
Après avoir joué dans un segment du film à sketches Paris, je t'aime (2005) et dans Je vais bien, ne t'en fais pas (2005), elle obtient une nomination dans la catégorie meilleur espoir féminin aux Césars 2007 pour son rôle dans le film Bamako (2006). En 2006, elle joue aussi dans Prête-moi ta main aux côtés d'Alain Chabat, qui lui offre ensuite un rôle dans son film Sur la piste du Marsupilami (2012).
Elle se diversifie et prépare sa première réalisation, Il faut quitter Bamako.