Alf and Alfhild
According to Gesta Danorum, Alfhild, daughter of the Geatish king Siward, was a shield maiden, who had her own fleet of viking ships, with crews of young female pirates, who raided along the coasts of the Baltic Sea.
As a young princess, Alfhild's chamber was guarded by a lizard and a snake, which scared away unworthy suitors. A Danish prince named Alf, also of Geatish descent, came to Geatland and defeated the animal guards. But Alfhild, advised by her mother, fled from Alf dressed as a man, and she became a shield maiden.
Alf and his Scanian comrade, Borgar, together with their Danish sea-warriors, searched for and eventually found Alfhild and her fleet by the coast of southern Finland. After some deadly fighting aboard the ships, Alfhild's helmet was knocked off, and she was recognised. Alf and Borgar ordered their men to stop fighting, and Alf embraced Alfhild, happy to finally have found her. She then decided to lay off her warrior clothes and follow Alf to Denmark, where they got married.
Some years later, in a war fought against a revolting Danish viking clan, Alf and his brothers and their father king Sigar were killed. Only Alf's and Alfhild's daughter Gurid had survived of the royal family. After being queen for a while, Gurid married one of Borgar's sons, Halfdan, and they had a son named Harald, who became the new king of Denmark.
According to the details in the saga, this would have taken place in the 5th century.
In popular culture
There are some variations to the story in later popular culture. Here Alfhild is most often called Awilda. (Other spellings: Alwilda, Alvilda, Alvild, Alvilde, Alfhilda, Avilda, Alvida, Altilda, Ælfhild).
Here, under the name of Alvida, she's figuring in a modern Dutch musical: 
The story about Alf And Alfhild has also been made into Italian operas.
In 1731, "Alvilda regina de' Goti", by Antonio Vivaldi.