Awal mula nama ini masih menjadi perdebatan. Sebagian kelompok mengambil kisah orang-orang Yunani yang menemukan air di lembah tandus Arabia dan kemudian menamakannya dengan Hydreumata atau sumber air. Sementara sebagian yang lain mengambil kisah orang-orang Arab kuno, dari zaman sebelum orang-orang Yunani mencapai lembah Arabia. Alkisah, dahulu kala Lembah Arabia merupakan tempat orang-orang barbar yang suka berperang dan saling membunuh. Kisah kejantanan dan keperkasaan mereka dalam perang selalu mereka banggakan dan mereka luapkan dalam bentuk puisi, sya'ir dan juga memberi pujian kepada pahlawan-pahlawan dari suku-suku dan kabilah mereka masing-masing. Pada waktu itu di bagian selatan lembah Arabia (Hadramaut) tinggal seseorang yang paling ditakuti oleh semua keluarga, bani, suku dan kabilah di seluruh arab. Orang tersebut bernama Amir Bin Qahtan, dia ditakuti karena keberaniannya, kejeliannya dan keperkasaannya. Setiap kali Amir Bin Qahtan berpartisipasi dalam sebuah perang maka tempat tersebut akan berubah menjadi lembah kematian. Karena itulah suku-suku Arab pada waktu itu menamai tempat Amir Bin Qahtan tinggal sebagai hadhramout yang berarti Hadhra=hadirmout=kematian yaitu di mana Amir Bin Qahtan berada, di situ pula kematian hadir bersamanya.
Pada masa pasca-Muhammad, kebanyakan dari mereka memeluk Islam dan menjadi pedagang dan petualang yang menghubungkan antara bagian timur benua Afrika (Sudan, Somalia, Eritrea) dengan bagian selatan benua Asia (India, Indonesia, Malaysia); dengan demikian menjadi pelaku Jalur Sutera laut.
Di Hadramaut juga tersebar ribuan keturunan Rasulullah yang berhijrah dari Makkah, dalam tujuan menghindari kekacauan yang ada di Makkah dan Madinah karena kaum Qaramitah yang ekstrem. Semula tanah Hadramaut penuh dengan kaum Khawarij dan SyiahZaidiyah, tetapi berkat dakwah para sayyid yang berhijrah ke Hadramaut,
Keturunan Rasulullah di Hadramaut biasanya adalah keturunan Sayyidina Husein yang melewati jalur nasab Sayyid 'Alawi bin Ubaidillah bin Ahmad al Muhajir ila Allah bin Isa ar-Rumi bin Muhammad an-Naqib bin Ali al-Uraidhi al Huseini disebut Bani 'Alawi (Ba'alawi) . Dan mereka, banyak yang berhijrah ke Nusantara.
Kebanyakan dari mereka berdagang dengan mengikuti arah angin barat dan timur. Hal inilah yang memaksa mereka menunggu selama beberapa bulan sebelum mereka kembali ke kampung halaman mereka. Selama masa penungguan inilah interaksi antara mereka dengan penduduk asli terjadi. Sebagian di antara para pedagang itu berdakwah dan juga menikahi gadis-gadis pribumi dan kebanyakan dari mereka menetap di sana.
Sebagian besar kaum keturunan Arab di Indonesia umumnya berasal dari wilayah ini. Ini dapat ditelusuri dari nama-nama marga mereka, seperti Al Amri, Alaydrous, Badjubier, Bawazier, Al Khered, Al Kaff, Al Attas, Al Kathiri, Bin zagr, Bin Abdat, Sungkar, Al Habsyi, dan lain sebagainya.