Look at how Alexander went about it. Aside from the occasional batches of reinforcements from Macedonia he was pretty darn soon enlisting Persians for pretty much everything...