בשנת 1984 החלו חזה ואלוני בפרויקט שאפתני: אלבום שכל שיריו יהיו שירי עם תימניים, שאותם תבצע חזה כמחווה למורשתה. תחילה הקליטה שני שירים לניסיון: "גאלבי", שנכתב והולחן על ידי אהרן עמרם, ו-"אסאלק", למילותיו של ר' שלם שבזי עם לחן מאת עמרם. בהמשך בחר אלוני את שאר השירים, ואף לימד אותה כיצד לקרוא את הטקסט בהטעמה תימנית. חזה הקדישה חצי שנה להקלטות, כשדגש רב מושם על איכות קולית וטכנית. האלבום, שירי תימן, יצא בדצמבר 1984 וחזה חידשה בו שירים תימניים ישנים ממגוון של תקופות ומקורות, מסוף המאה ה-17 (של רבי שלום שבזי), ומתקופות מאוחרות יותר, בעיבודים חדשים של בני נגרי. שלושה משירי התקליט הושרו בערבית וכל השאר היו בעברית, בנעימה תימנית, והעיבודים שנעשו לתקליט כללו שילוב מקורי של צלילים ומקצב עממי תימני עם כלים ותזמור קלאסיים. כשיצא האלבום, שהיה אחר כך לפריצת הדרך של חזה מחוץ לישראל, הוא הושמע רק בתוכניות הזמר המזרחי; באף תוכנית רדיו אחרת לא גילו עניין בשירי האלבום, שהיה שונה באופיו מהמוזיקה שהייתה מקובלת אז בזרם המרכזי. אלוני פנה ליאיר ניצני לצורך הכנת רמיקסים, וניצני היפנה אותו ליזהר אשדות, שהכין את הרמיקס לשיר "גאלבי". לאחר אי-ההתעניינות המתמשכת נשלח השיר לאנגליה על ידי צעיר אנגלי בשם גרנט אשר גילה בו עניין. מספר עותקים של התקליט ושל הסינגלים המחודשים הגיעו אל חברת התקליטים האנגלית "Ace Records". בחברה התרשמו מאוד, קנו את זכויות התקליט מ"הד ארצי" ושיווקו אותו בשם Fifty Gates Of Wisdom (חמישים שערי חוכמה). התקליט נמכר באנגליה, זכה לשבחי הביקורת של עיתוני המוזיקה היוקרתיים ביותר והחל את הצלחתה הבינלאומית של חזה.
המשך הקריירה בישראל.
ב-1984, לראשונה מזה ארבע שנים, הפסידה חזה את תואר "זמרת השנה" לירדנה ארזי, שהייתה יריבתה התקשורתית. האחרונה ניסתה במשך מספר שנים לפרוץ אל השוק המקומי כזמרת סולו לאחר פרידתה מ"שוקולד מנטה מסטיק", ובשנה זו הצליחה להעפיל אל הפסגה. מנקודה זו החל מאבק ממושך בין מועדוני המעריצות של שתי הזמרות, ששיאו היה בהופעה של ארזי באמפיתיאטרון וואהל בתל אביב, כשמעריצה של חזה ירתה על שמלתה דיו מתוך אקדח צעצוע. מלחמה תקשורתית התחילה בין שתי הזמרות, אשר לובתה בידי מעריצותיהן, והגיעה לסופה כאשר השתיים הודיעו כי התחרות אינה ביניהן אלא בין המעריצות.
באותה שנה שודרה בערוץ הראשון תוכנית הספיישל "מערב עד שחר" שכללה את מיטב להיטיה של חזה עד לתקופה זו בביצועים מהופעותיה בבסיס חיל האוויר ביפו וכן במועדון צוותא בתל אביב; קלטת וידאו של התוכנית יצאה ב-1988 בארצות הברית בלבד בשם "From Dusk To Dawn" ("מערב עד שחר" בתרגום לאנגלית), דרך חברת "Ergo Media".
באפריל 1985 יצא האלבום אדמה. האלבום, שבמקור תוכנן לכלול שירים שכולם פרי שיתוף פעולה בין חזה ונעמי שמר ולהיקרא "התחדשות", כלל לבסוף שירים של יוצרים ותיקים כגון: סשה ארגוב, יעקב אורלנד, משה וילנסקי ואפי נצר, לצד היוצרים הצעירים של התקופה, כדוגמת אהוד מנור ונורית הירש. להיטי האלבום היו שיר הנושא, "גורל אחד", ו-"מישהו הולך תמיד איתי". מתוך התכנון המקורי נותר רק שיר אחד, "התחדשות". האלבום נמכר ב-40 אלף עותקים והגיע למעמד של אלבום פלטינה. עוד באותה שנה הוציאה חזה את שירי מולדת ב', שהיווה המשך לקודמו; אלבום זה נמכר גם הוא ב-40 אלף עותקים.
באותה השנה הושקה בובת שעווה בדמותה במוזיאון השעווה הישראלי.
ב-1986 הוציאה חזה אלבום אוסף ראשון, אלבום הזהב, שכלל את להיטיה הגדולים עד אותה עת. בנוסף כלל האוסף גם גרסה באנגלית לשיר "איתך הלילה" וגרסאות בצרפתית לשירים "גבריאל" ו"מנגינת הלב". כמו כן, האלבום כלל שירים חדשים באנגלית שהופיעו בקלטת הווידאו שיצאה גם היא באותה שנה, "פנטזיה".
באותה שנה ניסתה חזה לעדכן את הסאונד המוזיקלי בסגנונה וחברה עם יזהר אשדות להפקת האלבום ימים נשברים שכלל סאונדים ואפקטים עדכניים וסגנון מעט יותר רוקיסטי משירי הפופ ששרה עד כה. כמעט כל המילים והלחנים באלבום נכתבו על ידי חזה עצמה. מסע הופעות בבימויו של צדי צרפתי ובהפקתו של יוסי פלג קידם את האלבום, והוא הניב להיטים כמו שיר הנושא, "הכאב הזה", "בוא ונגן אותי", "להמשיך לצעוד" ו-"כל הקלפים" / "ליידי". כ-30 אלף עותקים נמכרו מהאלבום והוא הגיע לאלבום זהב.
בשנת 1987 הקליטה חזה את האלבום שירי מולדת ג', שיצא לרגל חגיגות 40 שנה למדינת ישראל. ב-3 בפברואר אותה שנה ניצלה מהתרסקות מטוס צסנה שהיה אמור להחזיר אותה מהופעה בבסיס חיל האוויר נבטים לתל אביב. באותה שנה השתתפה בפרק מיוחד לפורים של התוכנית "זהו זה!" וכן בפסטיגל, שבו זכתה במקום השני עם השיר "ארבעים".
הקריירה הבינלאומית.
מאז ההצלחה באירוויזיון והצלחת האלבום שירי תימן מחוץ לישראל נעשתה חזה לזמרת מבוקשת גם מחוץ לישראל, בעיקר באירופה. מעמדה מחוץ לישראל הלך והתחזק ואיתו גם הביקושים להופעות. הגרסה המחודשת של "גלבי" כבשה את המצעדים. חזה התראיינה בתוכניות אירוח הפופולריות ובעיתונים נחשבים, וקמו לה מעריצים גם מחוץ לישראל. כדי לקדם את הקריירה הבינלאומית היא הקליטה אלבום שלם בצרפתית בשם "Aime Moi" (אהוב אותי), שכלל גם חידושים בצרפתית לשירים עבריים שהצליחו. לבסוף יצאו מספר סינגלים מן האלבום, אך הוא לא יצא במלואו. במקביל היא לא זנחה את הקריירה בישראל והמשיכה לקיים הופעות, ואף לשחק במחזמר "עוץ לי גוץ לי".
ב-1987 תבעה חזה צמד ראפרים אמריקאים בשם אריק B וראקים אשר סימפלו את קולה מהשיר "Im Nin'alu" לשירם "Paid in Full". אלוני, שראה את ההצלחה האדירה של הסימפול, החליט לקחת את אותה גרסה מחודשת של "Im Nin'alu" מ-1984, לערוך אותה מעט ולשלב בה קטעים באנגלית שכתב, שיושרו על ידי חזה. הדבר נעשה והתוצאות לא אכזבו: ביוני 1988 הגיע השיר לראש מצעד הפזמונים בגרמניה ושהה שם תשעה שבועות רצופים. הסינגל נמכר ביותר משלושה מיליון עותקים. באותה שנה זכתה חזה בתואר זמרת השנה בגרמניה. כך יצא שדגימת קולה לגרסת "Im Nin'alu" של הראפרים האמריקאים קידם את מכירותיה של חזה מחוץ לישראל והביא לה פרסום רב.
חזה התפרסמה לא רק באירופה ובאמריקה, אלא גם במזרח הרחוק ואפילו בארצות ערביות כמו תימן. בשנת 1988 יצא אלבומה Shaday, שכלל את השירים "גלבי" ו-"Im Nin'alu" בתוספת שני תרגומים לשירים מתוך האלבום ימים נשברים ועוד שירי דאנס אתניים. אלבום זה נמכר עד סוף השנה בלמעלה ממיליון עותקים באירופה ובעשרות אלפי עותקים בארצות הברית. מלבד הגרסאות המחודשות והמצליחות ל-"Im Nin'alu" ו-"גאלבי", בלטה רצועה נוספת מתוך התקליט – "עזה כמוות" (שהוצג בשם האנגלי: "Love Song"). השיר, שהוא בעצם חידוש לשיר של חזה מאלבום הסולו הראשון שלה, מכיל קטע משיר השירים המדגיש את עוצמתה ואת ייחודה של האהבה. בגרסה המחודשת אין שום כלי נגינה (א-קפלה) ויש רק אפקט הד קל ברקע. יכולתה הקולית של חזה מודגשת ביותר בשיר הזה, ומסיבה זו השתמשו יוצרים בעולם בשיר זה ליצירותיהם. באותה שנה זכתה חזה במקום הראשון בטקס "אריה הזהב" בגרמניה. ההצלחה מחוץ לישראל לא אפשרה לחזה להמשיך ולהוציא תקליטים גם בישראל, ועל כן היא נעדרה למספר שנים בעודה מתרכזת בקריירה מחוץ לישראל.
ב-1989 הוציאה את האלבום Desert Wind, שזכה להצלחה רבה כאשר נמכר בכחצי מיליון עותקים. מספר שירים ממנו, כמו "Ya Ba Ye" ו-"Wish Me Luck", היו ללהיטים. בנוסף, סיבוב ההופעות של האלבום זכה להצלחה מרובה וכלל שני הישגים חסרי-תקדים עבורה: ראיון והופעה בתוכניתו של מלך הטוק שואו האמריקאי ג'וני קרסון, וראיון בתוכנית הבוקר האמריקנית "The Today Show". שיר זה הפך ללהיט באירופה ובארצות הברית. באותה שנה (1989) ייצגה חזה את ישראל עם השיר "Im Nin'alu" בפסטיבל המוזיקה הבינלאומי של טוקיו שביפן וזכתה במקום הראשון. באותה עת סירבה חזה, ממניעים דתיים, לבקשת הוותיקן לשיר בפני האפיפיור יוחנן פאולוס השני. חזה הפכה לזמרת מוערכת במחוץ לישראל עם הסגנון המוזיקלי החדש שלה ולסמל גאווה לישראל. מומחים לנושא מחוץ לישראל טענו שחזה היא בעצם הראשונה שהביאה לעולם מוזיקה אתנית בשילוב סגנון מערבי, ואחת היוצרות הראשונות בז'אנר "מוזיקת העולם".
בשנת 1990 זכתה חזה בתואר "הזמרת הישראלית הנמכרת ביותר בכל הזמנים" במונטה קרלו, וסירבה להצעתו של מייקל ג'קסון להצטרף אליו לסיבוב הופעות עולמי. באותה שנה הופיעה בפסטיבל הג'אז במונטרה שבשווייץ, והופעתה המצליחה גם הופצה על גבי תקליט בשנת 1997. באותה שנה גם השתתפה שלוש פעמים בפסטיבל סן רמו שבאיטליה.
בשנת 1992 השתתפה בהקלטת הרמיקס לשיר "מקדש האהבה 1992" של להקת סיסטרס אוף מרסי. השיר בוצע בסגנון רוק כבד, והיא תרמה את קולה בסלסולי רקע.
בשנת 1993 הייתה חזה למועמדת הישראלית הראשונה לפרס גראמי כזמרת מוזיקת עולם, בזכות אלבומה המצליח Kirya, שצעד שבועות רבים במקום הראשון במצעד המכירות של המגזין "בילבורד". האלבום כלל בין היתר שיר המבכה את גורלה של האישה בעולם השוביניסטי-שמרני ("Daw Da Hiya") וכן שני שירי חתונה מסורתיים של יהודי תימן.
באותה השנה השתתפה חזה בתחרות "מלכת היופי" כשופטת ואף שרה בתחרות את השירים "מחרוזת שירי רועים" ו-"תפילה"', וכן כתבה לזמר אורי פיינמן את השיר "האור" לקדם-אירוויזיון 1992.
באותה תקופה שיתפה פעולה עם גדולי הזמרים כמו איגי פופ, פול אנקה, סיסטרס אוף מרסי ופאולה עבדול. מלבד זאת, השתתפה בתוכניות אירוח נחשבות מחוץ לישראל, וגם שרה את שירי הנושא לסרטים "סחלב פראי" "האומנת" ו-"המלכה מרגו" ביחד עם המוזיקאי היוגוסלבי גוראן ברגוביץ'.