The earliest account of a candace was known as the Candace of Meroe, a queen of Nubia at the time of the military campaign of Alexander the Great. When she had heard that the ambitious conquerer was planning to invade Nubia, she prepared her armies to meet him with her riding an elephant. Assessing her armies in their military formation he decided to invade Egypt instead.
It was also believed that that two shared a brief romance.
The story comes from a book called "The Alexander Romance" by a certain Pseudo-Callisthenes, but there is no historical evidence to support this account as Alexander never even attacked Nubia and never went further in Africa than Egypt (and Nubia, or Kush was south of Egypt).