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