The history of the people of the Arabian Peninsula prior to the coming of Islam is one of the ebb and flow of small civilizations coupled with the nomadic cultures in the interior.
The earliest known peoples inhabited the peninsula from 10 to 20,000 years ago. Cave drawings indicate hunting and gathering, and a wide variety of animals, which indicates that the peninsula has dried out considerably in that time. The proximity to the Nile valley and by sea to the Indus region facilitated trade amongst those cultures.
The Dilmun, occupying what is now Bahrain, and the Magan, ranging in the area of present day Oman, profited from trade with the peoples of the Indus and Mesopotamia. The Saba and Himyar, in present day Yemen, were on the trade route with eastern Africa and the Egyptians. Dilmun was known for it's pearls. Saba (Biblical Sheba) was known for it's aromatics, such as Frankincense and myrrh, which were harvested almost exclusively in the interior from the Saban civilization. The Sabans also constructed a dam holding back 37.5 square miles of water for irrigation. The Romans called this Arabia Felix, or Happy Arabia.
The Saban culture dominated the south west of the peninsula until about 500 AD, when the dam broke and the Roman Empire converted wholesale to Christianity, decimating the spice trade (as frankincense and myrrh were used in burial rituals). They sedintary culture mostly converted back to nomads.
The Nabataeans inhabited the northwest of Arabia, just south of the Hebrews. They remained fiercely independent during the Roman times, sometimes fighting the Roman legions off, sometimes negotiating tribute, but either way they remained outside of direct Roman control for most of their existance.
These civilizations were sedentary, as opposed to the nomads that inhabited the interior.
The nomadic tribes that lived in the interior of the peninsula were first called Arabs by Hebrew and Assyrian writings in about the 5th century BC. It is not known where the word comes from, although it might have been what they refered to themselves as. The Arabs were breeders of livestock, and considered agriculture beneath them.
The social unit was the clan, which was a group of related families. In the absense of a more universal government, the clan provided the rules of conduct and protection for its members. Without this, an individual had no one to appeal to for justice for any act committed against him.
After the fall of the more sedentary cultures in the 5th and 6th centuries, the Bedouin culture began to flourish, its code of conduct and blood feuds and raiding were developed. In the centuries after the Roman Empire split, the Bedouins would form tribal confederations, giving chieftains more power. They raided Damascus and Palestine, and then sacked Jerusalem. They eventually played off of the Byzantines and the Persians, as they were constantly at war. Some of the confederations sided with the Byzantines, some with the Persians.