From 541 to 542 the Plague of Justinian, afflicted the Eastern Roman Empire (Byzantine Empire), including its capital Constantinople.
"The most commonly accepted cause of the pandemic is bubonic plague, which later became infamous for either causing or for contributing to the Black Death of the 14th century. The plagues' social and cultural impact during this period is comparable to that of the Black Death. In the views of 6th century Western historians, it was nearly worldwide in scope, striking central and south Asia, North Africa and Arabia, and Europe as far north as Denmark and as far west as Ireland.
"Until about 750, the plague would return with each generation throughout the Mediterranean basin. The wave of disease would also have a major impact on the future course of European history. Modern historians named this plague incident after the Eastern Roman Emperor Justinian I, who was in power at the time. He contracted the disease, but was one of a limited number of survivors" (Wikipedia article on Plague of Justinian, accessed 11-01-2010).
Giovanna Morelli et al "Yersinia pestis genome sequencing identifies patterns of global phylogenetic diversity," Nature Genetics, 31 October 2010 | doi:10.1038/ng.705, suggested a common origin for the Plague of Justinian and later pandemics of plague in the bacterial agent Yersinia pestis originating in China.