There was more than one attempt to get a Byzantine bride for young Otto. The later ruler, Emperor John I Tzimiskes, had been treated a little differently. He had been referred to as Roman Emperor and so was not insulted. A round of negotiations was led by Archbishop Gero of Cologne. (Liudprand might have been involved, since he spoke and wrote Greek and was familiar with Constantinople, but his previous encounter might have made him a detriment to diplomacy.)
John chose his niece Theophanu, who was 14. There were some concerns in the West. For one, she was not "Porphyrogeneta," which means "born to the purple," so she was less royal than Anna. Also, she was even "less royal" because she was the emperor's niece through his brother-in-law by marriage and not actually a member of there powerful Macedonian dynasty.
John I Tzimiskes had come to power by overthrowing Nicephorus II Phocas, and the Ottonians were concerned that John's status as a usurper would invalidate Theophanu's suitability and standing as a link to the Byzantine Empire. Otto was advised to send her back to Constantinople, but for whatever reason he was persuaded otherwise. They were wed by Pope John XIII on 14 April 972. (You can actually see the marriage charter here.) She was also crowned Holy Roman Empress on the same day. The illustration is of Christ blessing the young couple.
One historian claims that Otto I, her father-in-law, was very supportive until his death a year later. Theophanu was later very involved in the running of the empire: she is mentioned in one quarter of the imperial documents. Although she was from a different culture, which made many of Otto's subjects wary of her, the only serious difficulty was with her mother-in-law, Adelaide of Italy. Before we go on to see what kind of ruler Theophanu was, let's take a look at Adelaide starting tomorrow.