Yemenite Jews have a famous, longstanding affinity for Rambam. Before the time of Rambam, which rabbis were the most influential in Yemen? E.g. Rav Saadya Gaon, local rabbis, etc.
Please provide evidence.
A very thorough explanation, with numerous examples, of the mesoroh of the Teimonim from before the time of the Rambam until several centuries afterward is laid out in the introduction to an out-of-print book entitled Ha-Ri"f al Masekheth Hullin im Pirush be-Safah Aravith Me-Ehadh Me-Hakhmei Yahaduth Teimon.
This book was authored and edited by HaRav Yosef Qafih z"l (Mori Yusef) and was - if I remember correctly - his first academic work.
As will be explained in the introduction, the Teimonim followed the opinions of various go'onim - principally those of Rasa"g - until the publication of the Mishneh Torah whereupon they found it to be useful since it contained the majority of what they were practically following as pesaq halokhoh in Yemen anyhow. This is the view of Mori Yusef z"l and also accounts for the variances between the words of the Rambam and ancient Yemenite practice.
This book can no longer be found anywhere, save on the bookshelves of a very few number of collectors, but I have a scan of it that may be found HERE.
They generally followed the Geonim and other Halakhic Authorities in Bavel, and then when Rambam came along, whom the Rabbis in Bavel opposed, they only accepted after he wrote to them Iggereth Teman and Iggereth Te'hiyath HaMethim, the latter was in order to answer to them after the Rabbis in Bavel accused Rambam of not believing in te'hiyath hamethim. See the Iggereth as well as the numerous works on it