I highly recommend "Arabia and the Arabs: From the Bronze Age to the coming of Islam" by Robert Hoyland

He discusses Arabia's regions in chronological order which I highly appreciate.

For the record, I'm still finishing up this book and I suggest you look at book reviews before you purchase it. I personally like it and I'm learning a lot about my own history!