Some rights could have existed but we are talking about pre-history, so how society functioned then is not entirely known. And their conception of "rights" may be different to how we consider them now.

Rights need recognition (either explicit or implicit) by whatever society they are a part of, whether that is a hunter gatherer society or a modern state. We now have a society which is so complex that it encompasses the entire world and is why groups of people can violate rights, even if they personally never recognized that right.

Internationalism has made it so that rights can now supersede the State (due to bodies such as the UN making agreements between all nations) but they originally came into existence from the State.

When we were hunter gatherers, we had no rights apart from what our social group/village allowed us to have. When serfdom existed, serfs were granted rights by their lords in exchange for their servitude. When liberal democracy started, we were granted rights by the state in exchange for the responsibilities of living in a society.

Now that countries hold each other accountable, some rights are given to all of humanity regardless of nationality. Prior to this internationalism, a state couldn't violate a right, unless it was a right they previously gave to subjects and then revoked.

Have you listened to Tricot or Covet? They have some songs with some breathtaking guitar playing!