Actually, since the "Arab Empire" is a pretty rare if not unique event (some underpopulated, semi nomadic tribe conquering half the wolrd, we are talking about the arabian coasts here, not the endless asian steppes!) in most timelines it would be butterflied.
But the catholic church itself offers an excelent structure for an empire: A common religion (well, duh!), a common language, an excellent provincial sistem (diocesis, archidioceis and primatures) than can easily expand -as it has done OTL to cover literally the planet-, a clear and mostly stable election system for a new ruler. A change sometime before the fall of the west, and we could create a Pope/Emperor/Caliph position, than could take over the Empire. The bishops would secularize, or equivalent secular positions -hereditary, appointed ot any combination- and we would have a stable structure.
The _empire_ itself would not be stable, of course, some centuries the Pope is a mere figurehead under a "shogun" like the Japanese Warior States, some centuries he is a absolutist Sun King, some centuries the empire is broken into warlord in a cosntant civil war -but unlike OTL civil wars, those warlords eventual aim ouwld be to kake over the EMpire itself, the way chine always reformed after its civil war decades.