Complex sentence: Although Saint Katherine wasn't established as a city at that time, yet it was always part of the Egyptian Empire throughout history and it was part of the province of "Deshret Reithu".
Split into simpler sentences: Although Saint Katherine wasn't established as a city at that time. It was part of the province of "Deshret Reithu".