החודש לפני 30 שנה בדיוק, הופיעה דנה אינטרנשיונל לראשונה עם השיר סעידה סולטנה (המוכר גם כ-My Name Is Not Saida).
זה היה השיר הראשון של דנה, זמרת אלמונית באותה תקופה, שנכתב כפארודיה לשיר "My Name Is Not Susan" של וויטני יוסטון.
השיר הוצג לראשונה על הבמה במועדון "התאטרון" בינואר 1992, במסגרת מופע דראג שארגן עופר ניסים, שכבר אז היה מפיק מוזיקלי מוכר בקרב הקהילה הגאה. ניסים הציע לדנה, אז אנונימית לחלוטין, לקחת חלק במופע בו היא ביצעה חיקויים של זמרות כמו זהבה בן, ריטה ועופרה חזה. באחת ההופעות, לאחר שאחת המשתתפות חלתה ולא הגיעה, דנה עלתה לבמה וביצעה את הפרודיה לשיר של וויטני יוסטון "My Name Is Not Susan", כשבמהלכו כפארודיה סוזן הפכה לסעידה.
"התחלתי את החיים החדשים שבחרתי לעצמי, גיליתי את חיי הלילה", סיפרה דנה בראיון ל-Mako בספטמבר 2021, "חברותיי הטובות, שלישיית משפחת סעדיה, הכירו לי את עופר ניסים שהיה אז התקליטן של מועדון התיאטרון… שירזי ניהל אמנותית את להקת הדראג של המועדון, עם בגדים מהבית, פאות זולות ומילים גסות שמושתלות על שירים מוכרים. כוכבת המופע הייתה נתי נתן, נתנאלה. "סעידה סולטנה" אמור היה להיות השיר שלה – אבל היא לא הגיעה. עופרה התקשרה אליה והכוכבת הודיעה שבגלל מזג האוויר הסוער היא לא יוצאת מהבית… עופרה ניתקה ושאלה אותי: "אולי את תשירי את סעידה?". הסכמתי. הקהל קיבל את השיר ואותי בווליום גבוה מהמצופה של התלהבות".
הקהל אהב את הביצוע של דנה והשיר הפך ללהיט של המועדון איתו הופיעה דנה בכל ערב שישי. באחת ההופעות נכחו במקרה מגישי הרדיו עופר נחשון ודידי הררי, שהחליטו להשמיע בתכנית הרדיו שלהם הקלטה של השיר.
"קיבלתי הקלטה על סליל כזה, וזה אפילו עוד לא היה מוכן לרדיו", סיפר דידי בראיון לישראל היום שנת 2012, "נטרפתי מהקטע הזה בלי לדעת מי שרה אותו ומה הסיפור מאחורי הזמרת, אבל איך ששמעתי חשבתי שזה מדהים לתוכנית שלי. חטפתי את זה ועשיתי השמעה. התגובות היו מטורפות כי זה היה קטע משוגע לגמרי שהתאים לתוכנית".
השמועה על ההופעה התפשטה במהירות, ושדרנים ותקליטנים רבים חיפשו אחר עותק מוקלט. ניסים הציע לדנה להקליט את השיר, למילים שחיברו יחד, ולהפיץ אותו. למעט אחד הבתים בשיר, שזהה לבית הראשון מהשיר של יוסטון, שאר השיר הינו מקורי.
עם יציאתו השיר הפך ללהיט, ובאוגוסט 1992 דנה התראיינה לעיתון מקומי של תל אביב וחשפה את עצמה כזמרת השיר. בראיון זה סיפרה שהשדרנים הציגו אותה בתור "סעידה" ושהיא חששה שהכינוי הזה ידבק בה, ולכן היא בחרה לעצמה את השם – דנה. שם ה"משפחה" אינטרנשיונל יתווסף מאוחר יותר עם פרסום השיר 'דנה אינטרנשיונל'.
חברת התקליטים IMP Dance שילבה את השיר באלבום האוסף "Super Mix 13", ומאוחר יותר החברה פנתה לעופר ניסים להפקת אלבום מלא עם שירים של דנה, שלימים יהיה האלבום הראשון שלה. באלבום השיר יקבל גרסה חדשה שהיא המוכרת היום.
השיר זכה להצלחה גדולה בארץ, בעיקר בסצינת המועדונים. בנוסף הוא זכה להצלחה עצומה במדינות ערב, כשרוב העותקים שלו נמכרים באופן פיראטי.
כתבה בעיתון ידיעות אחרונות שפורסמה בינואר 1995 דיווחה על הדרך בה ניתן להשיג את ההקלטות של דנה אינטרנשיונל במצרים, שם היא לא מוכרת כ"דנה אינטרנשיונל" אלא רק כ"סעידה סולטנה".
"הקלטות של 'סעידה סולטנה' מוברחות למצרים דרך מעבר הגבול ברפיח", נכתב בכתבה, "בקיוסק על הקונה לומר את מילת הקוד 'שושו' מתוך אחד משיריה של דנה. לאחר מכן, הקונה חייב להוציא את הכסף ולתת את שמו המלא ומקצועו. רק אז המוכר פונה לאחד מעוזריו בבקשה להביא את הקלטת מהמחסן הרחוק. בינתיים השיר 'סעידה סולטנה' נשמע במועדונים וממכוניות חולפות בבירת מצרים".
בעקבות הצלחת השיר מגיע ארתור בראון, המלחין של השיר המקורי, לישראל לדי להפגש עם דנה ועופר ניסים. הוא חזר לארצות הברית עם עותק של השיר החדש והפיץ אותו דרך חברת התקליטים Cobra Records. השיר נחל הצלחה גם בארצות הברית כשבשיאו הגיע למקום החמישי במצעד הדאנס של ארצות הברית, ולהופעות ראשונות של דנה במועדונים בחו"ל.
בשנת 2002 הקליטה דנה גרסה מחודשת לשיר ובדצמבר 2014 פורסמה גרסה חדשה נוספת לשיר, בשיתוף פעולה עם ליין המסיבות "אריסה", תחת הכותרת "סעידה סולטנה 2015". הגרסה הופקה לרגל מופע בסגנון ערבי בכיכובה של דנה באותו שבוע במועדון. הגרסה לוותה בקליפ וידאו, בו דנה לא מופיעה.
