हालांकि सितारा देवी उस मुकाम पर पहुंच चुकी हैं जहां एक कलाकार लीजेन्ड बन जाता है लेकिन इस मंजिल तक पहुंचने के लिए उन्हें तमाम विरोधों का सामना करते हुए कड़ा संघर्ष करना पड़ा। जिस दौर में उन्होंने कथक सीखना शुरु किया उस समय किसी लड़की के नृत्य करने को अच्छी निगाहों से नहीं देखा जाता था। नाचने वालियां या लड़के ही कथक किया करते थे। सम्मानित परिवारों की लड़कियों से यह अपेक्षा नहीं की जाती थी कि वे कथक सीखें लेकिन सितारा देवी के पिता वैष्णव संप्रदाय के संस्कृत विद्वान पंडित सुखदेव महाराज ने कथक में धार्मिक कथावस्तु को शामिल करके अपनी बिरादरी के कडे विरोध और जाति से बहिष्कृत किए जाने के बावजूद अपनी पुत्रियों अलकनन्दा और तारा तथा पुत्रों चौबे और पांडे को यह शास्त्रीय नृत्य सिखाया।