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