La storia della capoeira è molto complessa e difficile da tracciare in maniera precisa, soprattutto per la carenza di documenti scritti a riguardo e per la distruzione di questi dopo l'abolizione della schiavitù in Brasile; di certo sappiamo che trae le sue origini dalla mescolanza di rituali di lotta e danza di alcune tribù africane già colonie dei portoghesi, catturate e fatte schiave in massa per essere deportati in Brasile.

Il 22 aprile 1500 Pedro Álvares Cabral sbarca in Brasile e dietro di lui la civilizzazione portoghese. I colonizzatori per risolvere il problema di manodopera schiava cominciano a catturare africani (più robusti fisicamente degli indios autoctoni, decimati dalle malattie portate dai colonizzatori). Gli schiavi venivano sfruttati nelle piantagioni (canna da zucchero, tabacco, caffè, ecc.) per molte ore al giorno, ritirandosi poi nelle Sem-Alas (sem = senza, ala = lato di muro), grandi e miseri dormitori sotterranei, bui e senza mura divisorie, vivendo in condizioni pessime. Con le ingerenze olandesi nelle colonie portoghesi (1624-1654) in Brasile gli schiavi approfittarono degli scontri per darsi alla fuga. Alcuni si organizzarono in comunità indipendenti, nei villaggi detti quilombos. Questo periodo fu sicuramente un catalizzatore dello sviluppo della capoeira. Uno di questi villaggi, Palmares, all'epoca probabilmente collocato nello Stato nordestino Alagoas, è assurto a simbolo della lotta degli schiavi contro i loro carnefici. Fondato nel 1610, il primo Palmares sopravvisse per più ottant'anni resistendo all'incalzare dei portoghesi; fu distrutto nel 1695 dopo un assedio di 5 anni e 9000 soldati impiegati.

I primi documenti che parlano di capoeira risalgono al 1624, si tratta di diari dei capi di spedizione incaricati di catturare e riportare indietro gli schiavi neri che tentavano di scappare. Questi documenti fanno riferimento ad uno strano modo di combattere, "usando calci e testate come fossero veri animali indomabili".

Il mito diffuso è che la capoeira fosse un modo per gli schiavi di allenarsi a combattere dissimulando, agli occhi dei carcerieri, la lotta con la danza. Questo può essere vero solo per uno stadio molto primitivo del suo sviluppo, perché in realtà la pratica della capoeira a partire dal 1814 venne vietata agli schiavi, assieme ad altre forme di espressione culturale, principalmente per impedirne l'aggregazione, anche se alcune fonti dicono che questa forma di arte marziale ha continuato ad esistere e svilupparsi considerando il fatto che sia sopravvissuta fino ai nostri giorni.

Il 1888 fu l'anno di liberazione dalla schiavitù, ma gli schiavi liberati non ebbero modo di integrarsi facilmente nel tessuto socio-economico. La capoeira fu presto associata alla delinquenza di strada, tanto da venire proibita a livello nazionale già dal 1892. La pratica della capoeira rimase clandestina (da questo deriva l'uso per ogni capoeirista di un apelido, un soprannome), spesso violenta e praticata solo nelle strade da individui malfamati, schedati appunto dalla polizia come capoeiras.

Nel 1930 la politica nazionalistica del presidente/dittatore Getúlio Vargas, in cerca di uno sport da promuovere come sport nazionale, dette l'opportunità a Mestre Bimba di riscattare la Capoeira con lo stile di "Lotta Regionale di Bahia", da lui ideato. Nel 1932 gli venne permesso di aprire la prima accademia nella quale impose anche delle regole di disciplina per ripulire la cattiva immagine che l'opinione pubblica aveva della Capoeira. Dopo una pubblica esibizione di Mestre Bimba e dei suoi allievi finalmente lo sport ebbe il suo riscatto, e cominciò la sua lenta ascesa. Nel 1974 la capoeira è stata riconosciuta come sport nazionale brasiliano. Nel 1957 Mestre Canela porta la capoeira in Italia, prima a Roma dove istruisce qualche allievo, poi a Viterbo.