The Byzantine Empire, called in period the Eastern Roman Empire or New Rome was centred around the city of Constantinople and represented the eastern bulwark of Christendom against the rise of Islam. Unlike western Europe, however, the Byzantines were Eastern Orthodox Christians, and not Roman Catholics.
Byzantium played an immensely important role in the Medieval era, providing a link with the ancient past of the Ancient Greeks and the Roman Empire but also dominating the trade and pilgrimage routes which were important to western Europeans. In addition, the efforts of the Byzantines stopped (or at least slowed) the advance of Islam, which was regarded as a mortal threat to Christian Europe.
The Crusades were partly caused (and heavily influenced) by Byzantium; in 1096 Alexius I Comnenus called for help repelling the Turks (who, having captured much of Asia Minor, threatened Constantiople itself and damaged the lucrative overland trade routes. The western Europeans, entranced with the "official" cause for war -- protecting the pilgrim routes and freeing Jerusalem responded in immense numbers, triggering the First Crusade.
Byzantine ceremony and politics alike were highly cosmopolitan and could often be very subtle and intricate -- hence our modern use of the word "Byzantine" to describe needlessly devious or complicated things. Byzantines were often distrusted by their more straightforward western European cousins because of this. See also Byzantine ceremony for details.
In period, the Byzantines often used a red banner with a white crescent and a six-pointed star as their symbol, contrasted with the traditional green banner and crescent carried by the caliphs of Islam.