Might this be The Blue Sword by Robin McKinley? From the author's website (archived page as a new website seems to be in process of being made):
This is the story of Corlath, golden-eyed king of the Free Hillfok, son of the sons of the Lady Aerin.
And this is the story of Harry Crewe, the Outlander orphan girl who became Harimad-sol, King's Rider, and bearer of the Blue Sword, Gonturan, the sword Lady Aerin carried, the sword only a woman may wield, for it will turn in the hand of a man.
At the beginning of the story, the protagonist Harry is abducted from the colonial outpost where she is staying with her brother. Her abductor is Corlath, the king of Damar, which is partially a client state of the empire from which Harry comes. (The dynamic is clearly modeled on the British in northwestern India and Pakistan.) After her abduction, Harry is trained in the saddle-less riding, animal husbandry, and magical fighting lore of Damar, until she is brought to the king's hidden citadel in the northern mountains.
There is a back and forth romance between Harry and Corlath. Eventually, when war threatens, they separate, and Harry takes a band of "western" warriors from her homeland to defeat the evil invaders, with the help of the titular blue sword that she received from Corlath's people.