I think he randomly shows up every so often in Yaksha's field. Look for any place that has a golden warrior icon. That indicates a special warrior NPC is present. (They might have special recruit conditions, such as the hero must defeat them, or you can only defeat them via a super-effective move KO.)
Not sure if he shows up in the main story, but I did manage to recruit him in the side story. (He had a Deino then instead, though.)
