My family (both sides) have done extensive family trees - it takes a LOT of patience and checking, double checking and triple checking to get it right.
On the Irish side we've gone back as far as Clonmacnois which is where the family name came from (they changed their name to mean "Followers of St Ciaran" [also spelt Kieran depending on whose version of history you read] which then got mis-interpretted and mis-spelled over time to become the current version) - we have no way of knowing what they were called before that.
I've been to Clonmacnois and it's quite cool knowing that my family had its roots there.
On the other side it's a bit tricker...... the culture in the middle east was a little more nomadic.