@Youngmarshall - Please, no. Don't convert! You can't very well be Prester John AND not be Christian!
The concerns are valid though (Except the Capital, I never placed it anywhere, that commentary confused me).
So we need preparation - perhaps the 1200s are largely focused on Africa, conquering territory from Ethiopia Proper, Nubia, Somali, down to Zimbabwe & Zanzibar - and as such having control over the ports - did the Somali or any of the other people on the East Africa coast have a strong naval tradition? This could be where Ethiopia develops its own navy from. Indian Ocean traders, perhaps through an alliance with the Indian Pandyan dynasty as they carve up the Chola Empire? An early leader who had a bit of a Roman fetish (i.e. encouraging urbanisation), combined with the Pandyan skill for water management could certainly lead to a boon for the African part of the Empire.
Followed by the second period - using that new Empire, now solidified after 100 or so years of wrestling control of the Indian Ocean trade networks, to apply pressure to Arab states - diverting trade to Ethiopian Ports, or even Persian Ports, depending on what undermines Alexandria and whoever controls Yemen the most. If there has been anyone rounding the Cape, then Zanzibar might become the major trade outpost for East Asian Trade, as Ethiopia sells directly to Europeans, and crashes the trading economies of the Middle East (which certainly would help weaken them).
Follow that up with cannons and gunpowder imported via trade with China, and you could have this Ethiopian Empire trash the economy of its targets, before bringing gunpowder armies backed by (simple) mass artillery north through Egypt - and this is an Empire that would certainly want to try and rebuild the Canal of the Pharaohs, now that they can increase their profits via that route.
That could be the basic outline for the first 100-200 years, which sets them up in Egypt, and as a major trade power.