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