The first states were mostly monarchies. They
were ruled by kings or queens. The earliest monarchies that we know
about are the ones in Sumer
and Egypt. These both
began around 3000 BC.
But it was not only the early states which had kings and queens. After all there are still many countries which have kings and queens even today.
Some other examples of places which were ruled by kings are Greece in the Late Bronze Age, as described in Homers' Iliad, the Etruscan cities in northern Italy, including Rome between about 700 and 500 BC, China in the Warring States period, the Early Medieval kingdoms of Western Europe and Africa like the Visigoths, the Vandals, the Franks, Ethiopia and Mali, and the later medieval kingdoms (both Christian and Islamic) of France, England, and Spain.
While there have been many more men in power than women, there have always been women rulers too. There were women who ruled Egypt, like Hatshepsut and Cleopatra, and women who ruled the Byzantine Empire, like Irene. There were women who ruled southern France, like Eleanor, and women who ruled Castile in Spain, like Isabelle, and women who ruled the kingdom of Kush in Africa, and the Empresses Lu and Wu Chao in China. Many other women held power without having the official title, often as regents for their sons or grandsons, like Agrippina and Julia Maesa in Rome, Pulcheria in Constantinople, or Blanche of Castile in France.