1929 में कांग्रेस अधिवेशन के बाद गांधीवाद से प्रभावित होकर खान साहब ने खुदाई खिदमतगार नामक संगठन की नींव रखी | इस संगठन की पहचान थी लाल कुडती | लोग उन्हें सुर्खपोश कहते | इस सामाजिक आन्दोलन ने अंग्रेजों की नींद उड़ा दी | अप्रैल 1930 में उतमान जई से पेशावर जाते समय नाकी थाने के समीप इन्हें एक बार फिर गिरफ्तार कर लिया गया | इनकी गिरफ्तारी की खबर जंगल में आग की तरह फ़ैल गई | चार सद्दा में हजारों लोग अपने क्रोध और क्षोभ का प्रदर्शन करने को एकत्रित हुए | 

अंग्रेजों का दमनचक्र चलने लगा | किस्सा खानी बाजार पेशावर में तो लगभग ढाई सौ लोग अंग्रेजों की गोली खाकर शहीद हुए | उतमान जई स्थित खुदाई खिदमतगार कार्यालय की दूसरी मंजिल से कार्यकर्ताओं को नीचे पक्की सड़क पर फेंका गया | उसके बाद उसमें आग लगा दी गई | लाल वस्त्र पहनने वाले हर व्यक्ति को बेरहमी से मारा-पीटा गया | इसके पश्चात डिप्टी कमिश्नर ने गरजते हुए लोगों से पूछा – क्या अब भी कोई सुर्खपोश बाकी है ?

डर के मारे किसी की जुबान खोलने की हिम्मत नहीं हुई | लेकिन मुहम्मद अब्बास खान नामक एक व्यक्ति को यह सहन नहीं हुआ | वह तब तक संगठन से जुडा भी नहीं था | वह दौड़कर अपने घर गया | लाल रंग देग में डालकर अपने कपडे रंगे और गीले लाल कपडे पहिनकर वापस लौटा और अंग्रेज डिप्टी कलेक्टर से कहा – ये हैं लाल बस्त्र, देखो मैंने पहिन रखे हैं |

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

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

अब तो डूबते को तिनके का सहारा जैसी स्थिति में इनके पास कांग्रेस से मदद माँगने के अलावा कोई चारा ही नहीं बचा | कांग्रेस के नेताओं ने साफगोई से कहा कि अगर आप लोग हमारे साथ भारत की स्वाधीनता की लड़ाई में सम्मिलित होने को तैयार हों तो हम भी आपकी मदद करेंगे | प्रांत के खुदाई खिदमतगारों का एक जिरगा (बैठक) हुआ, जिसमें कांग्रेस की बात मान ली गई | 
अंग्रेजों को जब यह समाचार मिला कि पठान लोग सामूहिक रूप से कांग्रेस में सम्मिलित हो गए हैं, तो उनके होश उड़ गए | उन्होंने खान साहब के पास सुलह के सन्देश भेजे किन्तु उन्हें जबाब मिला – अब तो हमने कांग्रेस के साथ रहने की कसम खा ली है, हम उसे नहीं तोड़ेंगे |

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

अंततः गांधी इरविन समझौते के बाद सभी राजनैतिक बंदी रिहा हुए | रिहा होने वालों में खान साहब सबसे अंतिम व्यक्ति थे | और वे भी तब रिहा हुए जब गांधीजी ने व्यक्तिगत रूपसे इसके लिए लार्ड इरविन से कहा | अब तक जन सामान्य में इनका नाम बादशाह खान या बाचा खान प्रचलित हो चुका था |

लेकिन यह रिहाई केवल कुछ समय की ही रही | 24 दिसंबर 1931 को बादशाह खान साहब को फिर गिरफ्तार कर लिया गया | इस बार उन्हें अपने प्रांत से दूर हजारी बाग़ जेल में रखा गया, ताकि ये अपने साथियों तक अपनी बात न पहुंचा सकें | इनके साथ इनके बड़े भाई डॉ. खान साहब, भतीजे व बेटे भी गिरफ्तार कर लिए गए | पर सबको अलग अलग जेलों में रखा गया | तीन वर्ष बाद जब रिहा हुए तब भी यह प्रतिबन्ध लगा दिया गया कि ये अपने गृह प्रदेश में नहीं जा सकते |

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

1936 में रिहाई के बाद भी इन्हें सीमा प्रांत में जाने की अनुमति नहीं मिली | तब तक 1937 में प्रांत की विधानसभा के चुनाव संपन्न हो गए व बड़े भाई डॉ. खान साहब केन्द्रीय विधानसभा के सदस्य निर्वाचित हो गए | निर्वाचित सदस्यों में बहुमत खुदाई खिदमतगारों का था, किन्तु अंग्रेजों ने कुटिलता पूर्वक सर नबाब साहबजादा अब्दुल कय्यूम के नेतृत्व में मंत्रिमंडल गठन करवाया, जिसके विरुद्ध छः माह में ही अविश्वास प्रस्ताव पारित हो गया | तथा डॉ. खान साहब के नेतृत्व में नए मंत्रिमंडल का गठन हुआ | तब कहीं जाकर बादशाह खान अपने प्रांत वापस जा पाए | 1939 में जब युद्ध शुरू हुआ तो भारत के समस्त प्रान्तों के कांग्रेस मंत्रिमंडलों के साथ सीमाप्रांत के मंत्रीमंडल ने भी त्यागपत्र दे दिया | 8 अगस्त 1942 को मुम्बई में कांग्रेस ने “अंग्रजो भारत छोडो” का प्रस्ताव स्वीकृत किया | और शुरू हुआ असहयोग आन्दोलन | अर्थात टेक्स देना और सेना में भर्ती निषेध | 

एक बार फिर स्वाधीनता की अलख जागते बादशाह खान को चार सद्दा से पैदल मरदान के लिए जाते समय मीरवस ढेरी नामक स्थान पर गिरफ्तार कर लिया गया | यहाँ खुशदिल खान नामक पुलिस अधिकारी ने इन्हें इतना पीटा कि इनकी तीन पसलियाँ टूट गईं | नाम खुशदिल और व्यवहार ? यहाँ से इन्हें हरिपुर जेल भेज दिया गया |

1945 में बादशाह खान रिहा हुए और उन्ही दिनों अविभाजित भारत के अंतिम आम चुनाव हुए | सम्पूर्ण भारत में यह चुनाव भारत और पाकिस्तान के प्रश्न को लेकर हो रहे थे | हिन्दू और मुस्लिम के प्रश्न पर | मुस्लिम लीग के लोग इसे मस्जिद और मंदिर अथवा इस्लाम व कुफ्र का चुनाव बता रहे थे | लेकिन पठानों को इस्लाम के नाम पर मूर्ख बनाना आसान न था | इसी कारण पूरे सरकारी सहयोग के बाद भी सीमा प्रांत में मुस्लिम लीग कि करारी हार हुई | हर जगह खुदाई खिदमतगार के उम्मीदवार विजई हुए |

अब समय आया अंग्रेजों के भारत से जाने का | गांधी जी ने जब बादशाह खान से पूछा तो उन्होंने स्पष्ट शब्दों में कहा कि विभाजन के अतिरिक्त हर योजना अच्छी है | वायसराय ने सम्पूर्ण भारत की असेम्बलियों के जनप्रतिनिधियों से पूछा कि वे भारत के साथ रहना चाहते हैं, अथवा पाकिस्तान के | किन्तु सीमा प्रांत की असेम्बली को यह अधिकार नहीं दिया गया | बल्कि दोबारा जनमत संग्रह का आदेश उन पर थोप दिया गया | दुर्भाग्यपूर्ण स्थिति यह रही कि कांग्रेस ने भी पठानों का साथ नहीं दिया | कांग्रेस कार्यसमिति की इस कठोरता, उपेक्षा और उदासीनता से बादशाह खान का दिल टूट गया | कांग्रेस ने न केवल उन्हें अपने से दूर फेंक दिया था, बल्कि एक प्रकार से हाथ पैर बांधकर शत्रुओं के हवाले कर दिया था | 

उन्होंने बार बार कहा कि शेष भारत के लिए अलग पैमाना और सीमा प्रांत के लिए अलग पैमाना क्यों ? और अगर जनमत संग्रह करना ही है तो पाकिस्तान अथवा पख्तूनिस्तान के नाम पर कराओ | पर उनकी आवाज नक्कार खाने में तूती की आवाज बनकर रह गई | खुदाई खिदमतगार संगठन ने जनमत संग्रह का बहिष्कार किया, पूरी सरकारी मशीनरी ने लीगियों के पक्ष में काम किया, सेना और पुलिस ने फर्जी वोट डाले उसके बाद भी उन्हें महज 50.1 प्रतिशत मत हासिल हो पाए, जो पूरी एक जाति के भाग्य का फैसला करने के लिए नितांत अपर्याप्त थे | 

जिस समय कांग्रेस कार्यकारिणी समिति ने भारत के विभाजन और सीमा प्रांत में जनमत संग्रह का फैसला लिया, वह बादशाह खान के लिए मृत्यु के फैसले जैसा था | आहत बादशाह खान की व्यथा गांधीजी के सम्मुख इन शब्दों में फूटी – हमने भारत की स्वाधीनता के लिए बहुत बलिदान किये हैं | लेकिन आप लोगों ने हमें छोड़ दिया है और भेडियों के हवाले कर दिया है | हमें खेद इस बात पर है कि हमने तो कांग्रेस को नहीं छोड़ा, लेकिन कांग्रेसियों ने हमें छोड़ दिया | 

और यह तो सर्व विदित तथ्य है कि अंग्रेज शासनकाल में 15 वर्ष जेल में गुजारने वाले बादशाह खान पाकिस्तान बन जाने के बाद भी अपने जीवन के शेष 18 वर्षों में से 15 वर्ष जेल में ही रहे |