Is the bold part correct?

Yes, but I would think that one would write something to the effect of: "Due to the leadership of our Chief Priest . . ."

One might also write: "By following our Chief Priest's leadership . . . "

Thanks, Setanta.

Following our Chief Priest’s leadership and the direction of our High Priest we converted many people to our religion.

Would it be correct if I rephrased the above as follows?

Under our Chief Priest’s leadership and following the direction of our High Priest, we converted many people to our religion.

That would be fine, Miss Tan. The problem with beginning the sentence with "following" is that it has a temporal meaning, as well as the simple meaning of the verb. "Following the fall of Richmond to the Federal armies, Lee's Army of Northern Virginia melted away until he was forced to surrender." Do you see? In that case, fallowing has the temporal meaning of what takes place after a particular event or passage in time.

Thanks, Setanta, for the analytical reply and the sentence illustrating the temporal meaning of "following".