हैहय वंश की कथा अत्यंत गौरवशाली है। हैहय के उत्तराधिकारी थे प्रसिद्ध धर्मनेत्र, जिनके पुत्र हुए कुन्ति, और कुन्ति के पुत्र थे सम्हता। सम्हता के उत्तराधिकारी बने राजा महिष्मान, और महिष्मान के पुत्र थे पराक्रमी रुद्रश्रेय। रुद्रश्रेय ने पूर्व में बताई गई वाराणसी नगरी में राज्य किया। उनके पुत्र हुए राजा दुर्दम, और दुर्दम के पुत्र थे बुद्धिमान और शक्तिशाली कनक। कनक के चार पुत्र हुए, जिनकी ख्याति संसार में फैली—कृतवीर्य, कृताग्नि, कृतवर्मा और कृतौजस। कृतवीर्य से जन्म लिया अर्जुन ने। यह राजा अर्जुन सहस्त्रबाहु के नाम से प्रसिद्ध हुए, क्योंकि वे सहस्त्र (हजार) भुजाओं के साथ जन्मे थे और सातों द्वीपों के अधिपति बने। उन्होंने दस हजार वर्षों तक घोर तप किया। कृतवीर्य अर्जुन ने अत्रि के पुत्र दत्तात्रेय की उपासना की, और दत्तात्रेय ने उन्हें चार परम वरदान दिए। सबसे पहले अर्जुन ने हजार भुजाएँ माँगीं, फिर दुष्टों को दंड देने और धर्मात्माओं द्वारा अधर्म को रोकने की शक्ति माँगी। साथ ही युद्ध में धर्मपूर्वक पृथ्वी को जीतने और अतिक्रमी शत्रु को मारने का अधिकार माँगा। इन वरदानों के बल पर उन्होंने सम्पूर्ण पृथ्वी, उसके सातों द्वीप, पर्वत और सातों समुद्रों से घिरी हुई भूमि को क्षत्रिय धर्म से जीत लिया। उनकी इच्छा से सचमुच उनके हजार भुजाएँ प्रकट हुईं, और उनका रथ तथा ध्वजा भी उत्पन्न हुई—ऐसा सुना गया है। उस बुद्धिमान राजा ने दस हजार यज्ञ निर्बाध रूप से द्वीपों में किए। उनके सभी यज्ञ दान से परिपूर्ण थे, सबमें स्वर्ण की यूपशिलाएँ और स्वर्णमयी वेदियाँ थीं। उनके यज्ञों में देवता अपने विमान में आकर शोभायमान होते, और गंधर्व-अप्सराएँ वहाँ सदा सुशोभित रहतीं। एक यज्ञ में, गंधर्व नारद ने कृतवीर्य अर्जुन की महिमा देखकर गीत गाया। उन्होंने कहा कि क्षत्रियजन यज्ञ, दान, तप, वीरता या विद्या से कृतवीर्य का मार्ग नहीं प्राप्त कर सकते। कृतवीर्य अर्जुन तलवार, चक्र, धनुष-बाण से सुसज्जित होकर रथ पर चढ़े, योगी की भाँति सातों द्वीपों में घूमते और चोरों की रक्षा करते थे। वे पचासी हजार वर्षों तक राज्य कर सार्वभौम सम्राट बने, और सभी रत्नों से परिपूर्ण थे। उन्होंने स्वयं ग्वाले, खेतों के रक्षक और योगबल से अर्जुन मेघ (वर्षा लाने वाले) का रूप भी धारण किया। उनके धनुष की प्रत्यंचा से कठोर हुई हजार भुजाएँ शरद् सूर्य के समान सहस्त्र किरणों से चमकती थीं। उन्होंने माहिष्मती में कर्कोटक नाग के पुत्र को युद्ध में पराजित कर वहीं स्थापित किया। वर्षा ऋतु में यह राजा समुद्र की तीव्र धारा को खेल-खेल में पार करते और विपरीत प्रवाह में आनंद लेते। जब वे तट पर प्रतिद्वंद्वी पुष्पमालाओं से सजे विहार करते, तब नर्मदा उनकी लहरों की भृकुटि से भयभीत होकर संकोच से समीप आती। वे अकेले ही हजार भुजाओं से महान समुद्र में उतरते और वर्षा से फूली नर्मदा को वेग से प्रवाहित करते। जब वे समुद्र को अपनी हजार भुजाओं से उद्दीप्त करते, तब पाताल में रहने वाले दानव भी स्थिर हो जाते। वे समुद्र को ऐसे मथते कि बड़ी-बड़ी तरंगें उठतीं, मछलियाँ और व्हेल डूब जातीं, और वायु से टकराकर झाग के गुच्छे ऊपर उड़ते, जिससे समुद्र अगम्य हो जाता। देवता भी, मंदार पर्वत की मथानी की तरह समुद्र के मंथन से चकित हो, अमृत की उत्पत्ति की आशंका करने लगते। उस समय महान सर्प भी शांत हो, उनके सिर सांझ के समय केले के तनों की तरह स्थिर हो जाते। इसी प्रकार अर्जुन ने अपने धनुष पर पाँच बाण चढ़ाए और लंका में बलपूर्वक रावण और उसकी सेना को चकित कर दिया। अर्जुन ने रावण को जीतकर बाँध लिया और उसे माहिष्मती लाकर बंदी बना दिया। तब पुलस्त्य मुनि अर्जुन के पास आए और उन्हें प्रसन्न कर रावण को मुक्त कराया। जब पुलस्त्य ने अर्जुन को शांत किया, तब उनके हजार भुजाओं से धनुष की प्रत्यंचा का शब्द उठा। वह शब्द सहस्त्र मेघों की गड़गड़ाहट या इंद्र के वज्र के प्रहार के समान था। परंतु भाग्य के विधान से भृगुवंशी परशुराम ने उन्हें पराजित किया। वहाँ उनकी सोने की तरह दमकती हजार भुजाएँ काट दी गईं। क्रुद्ध होकर अर्जुन ने शाप दिया— "हे हैहय, तुमने मेरी प्रसिद्ध वनस्थली को जलाया है, अतः कोई अन्य यह कठिन कार्य करेगा और वह तुमसे सब कुछ छीन लेगा।" फिर कहा गया कि तुम्हारी हजार भुजाएँ पहले काटी जाएँगी, और भृगुवंश का एक पराक्रमी, तपस्वी ब्राह्मण तुम्हें मारेगा। उस समय परशुराम ही शाप के कारण उनकी मृत्यु बने, और यह वरदान स्वयं राजर्षि अर्जुन ने पहले माँगा था। उनके सौ पुत्र हुए, जिनमें पाँच महान रथी, शस्त्रकुशल, बलशाली, धर्मनिष्ठ और पराक्रमी थे। हे नरश्रेष्ठ, उन पुत्रों में शूरसेन, शूर, धृष्ट, क्रोष्ट्री, जयध्वज, वैकर्त और अवंति प्रमुख थे। जयध्वज के पुत्र हुए पराक्रमी तालजंघ, जिनके अपने पुत्र तालजंघ कहलाए और उनकी संख्या सौ थी। इन महान हैहयों में पाँच वंश विशेष प्रसिद्ध हुए—वितीहोत्र, शर्याती, भोज, अवंति और वृतिhoत्र। यही है हैहय वंश की अद्भुत और महिमामयी कथा।