Capoeira spent its formative years in slavery. The history of the art goes back more than five hundred years, to when the Portuguese began to capture Africans to work in Brazil. The exact origins of Capoeira are both unclear and largely unstudied by academic historians, but a number of elements have come to be accepted.
It is obvious that Capoeira is a mingling of many different cultures, as Africans who called wildly different regions "home" were mixed together as slaves. Capoeira might, at least in some part, simply been a way for them to communicate with each other culturally. Certainly the culture of the slave masters influenced its formation as well, establishing for example the common language, Portuguese, that everyone knew.
Capoeira might have been a form of self-defense against the slave masters, or a way of settling disagreements between the slaves themselves, or it might have been carried almost directly from older African traditional dances. It is definitely a fighting art, and one practiced by those who were watched and owned, and that means it hid itself. It hid violence in dance, and trickery and cleverness in playfulness.
One of the oldest Capoeira stories is of a quilombo named Palmares. When a slave escaped his masters, he or she had two paths to follow: Either run south to another country (analogous to fleeing north in the United States), or make his or her way to one of the escaped slave communities hiding in the jungle or mountains. These communities, which ranged from small hidden settlements to collections of several villages, were constantly under attack by those who wanted to recover their slaves or simply combat the rebellion implicit in the quilombos, societies of escaped slaves, existing at all.
The largest and most famous quilombo was Palmares. Its first recorded leader was named Ganga Zumba, who was appointed directly by a powerful orixa (a powerful deity-like being featured in the beliefs of the Yoruba in Western Africa). He ruled for a very long time through numerous sieges by the Portuguese, who, despite their determination, never seemed able to more than scratch the surface of Palmares. The settlements were too well hidden, and were protected by hundreds of warriors skilled in Capoeira who could move silently through the mountainous jungle.
Finally, the Portuguese resorted to offering Ganga Zumba a deal: If he led his people down out of the mountains to some awful, desert valley that the Portuguese had set aside for them, every single citizen would be granted their freedom. Despite the obvious manipulation to eliminate Palmares as a thorn in the side of the slave-masters, many of the escaped slaves, including Ganga Zumba, were so tired by decades of being repeatedly attacked and invaded, were willing to accept the bad deal.
Ganga Zumba accepted, but one of the citizens of Palmares, Zumbi, passionately refused to submit to the Portuguese. He was able to get most of the people of Palmares behind him, and in the end, because Ganga Zumba refused to break his word to the Portuguese, he alone with just one village of Palmares moved to the offered valley. Seeing just how much they had been taken advantage of, however, he realized what a mistake he had made and gave his life to convince those who had followed him to return to the mountains and follow Zumbi.
Zumbi brought the war down from the mountains to raid the towns of the Portuguese, turning the tide and making it critical to the masters to end Palmares. In desperation, they hired a famous mercenary, Domingo Jorge Velhos, who led a large army toward Palmares, even dragging cannons through the jungle. The escaped slaves, seeing the high stakes of the battle, burned their fields and villages and retreated to a central fortress. After days of siege and fighting through clever traps laid by Zumbi's army, Domingo Jorge Velhos finally broke into the fortress and massacred most of the people of Palmares. Zumbi escaped, but was tracked down in the jungle and shot.
The Portuguese believed that after decades, they had finally destroyed the largest and greatest quilombo. They underestimated, however, the power that Zumbi had had as a symbol and leader; the few survivors of the siege gathered together under a youth who had run with Zumbi in his final escape. Palmares lasted as a smaller force for many more decades, and was never found or completely eradicated. Indeed, it outlasted the end of slavery in Brazil.