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