The earliest reported date of the arrival of Norman knights in southern Italy is 999, although it may be assumed that they had visited before then. In that Year, according to some traditional sources of uncertain origin, Norman pilgrims returning from the Holy Sepulchre in Jerusalem via Apulia stayed with Prince Guaimar III in Salerno. The city and its environs were attacked by Saracens from Africa demanding payment of an overdue annual tribute. While Guaimar began to collect the tribute, the Normans ridiculed him and his Lombard subjects for cowardice, and they assaulted their besiegers. The Saracens fled, booty was confiscated and a grateful Guaimar asked the Normans to stay.

Ranulf and Sergius recaptured Naples. In early 1030 Sergius gave Ranulf the County of Aversa as a fief, the first Norman lordship in southern Italy. Norman reinforcements and local miscreants, who found a welcome in Ranulf's camp with no questions asked, swelled Ranulf's numbers. In 1035, the same Year William the Conqueror would become Duke of Normandy, Tancred of Hauteville's three eldest sons (William "Iron Arm", Drogo and Humphrey) arrived in Aversa from Normandy.

In 1038 Byzantine Emperor Michael IV launched a military campaign into Muslim Sicily, with General George Maniaches leading the Christian army against the Saracens. The future king of Norway, Harald Hardrada, commanded the Varangian Guard in the expedition and Michael called on Guaimar IV of Salerno and other Lombard lords to provide additional troops for the campaign.

Wars between the Normans and the Byzantine Empire were fought from c. 1040 until 1185, when the last Norman invasion of the Byzantine Empire was defeated. At the end of the conflict, neither the Normans nor the Byzantines could boast much power as by the mid-13th century exhaustive fighting with other powers had weakened both, leading to the Byzantines losing Asia Minor to the Ottoman Empire in the 14th century, and the Normans losing Sicily to the Hohenstaufen.

The Battle of Civitate was fought on 18 June 1053 in southern Italy, between the Normans, led by the Count of Apulia Humphrey of Hauteville, and a Swabian-Italian-Lombard army, organised by Pope Leo IX and led on the battlefield by Gerard, Duke of Lorraine, and Rudolf, Prince of Benevento. The Norman victory over the allied papal army marked the climax of a conflict between the Norman mercenaries who came to southern Italy in the eleventh century, the de Hauteville family, and the local Lombard princes.

After 250 years of Arab control, Sicily was inhabited by a mix of Christians, Arab Muslims, and Muslim converts at the time of its conquest by the Normans. Arab Sicily had a thriving trade network with the Mediterranean world, and was known in the Arab world as a luxurious and decadent place. It had originally been under the rule of the Aghlabids and then the Fatimids, but in 948 the Kalbids wrested control of the island and held it until 1053. During the 1010s and 1020s, a series of succession crises paved the way for interference by the Zirids of Ifriqiya. Sicily was racked by turmoil as petty fiefdoms battled each other for supremacy. Into this, the Normans under Robert Guiscard and his younger brother Roger Bosso came intending to conquer; the pope had conferred on Robert the title of "Duke of Sicily", encouraging him to seize Sicily from the Saracens.

During the time of the First Crusade, the Byzantines were able to utilize, to some extent, Norman mercenaries to defeat the Seljuk Turks in numerous battles. These Norman mercenaries were instrumental in the capture of multiple cities. It is speculated that, in exchange for an oath of loyalty, Alexios promised land around the city of Antioch to Bohemond in order to create a buffer vassal state and simultaneously keep Bohemond away from Italy. However, when Antioch fell the Normans refused to hand it over, although in time Byzantine domination was established

In 1147 the Byzantine empire under Manuel I Comnenus was faced with war by Roger II of Sicily, whose fleet had captured the Byzantine island of Corfu and plundered Thebes and Corinth. However, despite being distracted by a Cuman attack in the Balkans, in 1148 Manuel enlisted the alliance of Conrad III of Germany, and the help of the Venetians, who quickly defeated Roger with their powerful fleet

Holy Roman Emperor, Henry VI invaded Sicily and was crowned King, ending Norman rule in southern Italy.

Unlike the Norman conquest of England (1066), which took a few years after one decisive battle, the conquest of southern Italy was the product of decades and a number of battles, few decisive. Many territories were conquered independently, and only later were unified into a single state. Compared to the conquest of England, it was unplanned and disorganised, but equally complete.

Institutionally, the Normans combined the administrative machinery of the Byzantines, Arabs, and Lombards with their own conceptions of feudal law and order to forge a unique government. Under this state, there was great religious freedom, and alongside the Norman nobles existed a meritocratic bureaucracy of Jews, Muslims and Christians, both Catholic and Eastern Orthodox. The Kingdom of Sicily thus became characterized by Norman, Byzantine, Greek, Arab, Lombard and "native" Sicilian populations living in harmony, and its Norman rulers fostered plans of establishing an empire that would have encompassed Fatimid Egypt as well as the crusader states in the Levant.

The Norman conquest of southern Italy began an infusion of Romanesque (specifically Norman) architecture. Some castles were expanded on existing Lombard, Byzantine or Arab structures, while others were original constructions. Latin cathedrals were built in lands recently converted from Byzantine Christianity or Islam, in a Romanesque style influenced by Byzantine and Islamic designs. Public buildings, such as palaces, were common in larger cities (notably Palermo); these structures, in particular, demonstrate the influence of Siculo-Norman culture.