>Seems like you need some kind of divine recognition, as otherwise you're just a dictator.

I'd argue you have it backwards there. You start as a dictator (you and a bunch of people who agree with you take over some part of land, congrats you're the King) then the legitimacy comes from you and your family holding on to it till everyone's used to it.