Płyta Kayah/Bregović, wydana w kwietniu 1999 roku, była największym sukcesem komercyjnym w całej karierze Kayah i jednym z największych bestsellerów w całej historii polskiej fonografii. Osiągnęła status "Diamentowej Płyty", rozchodząc się w ilości ponad 700 tysięcy egzemplarzy. Album stanowił udane połączenie współczesnego popu i folkloru bałkańskiego z rodzimą tradycją ludową. Zawierał muzykę góralską, cygańską, śpiewy biesiadne, a nawet echa kolędy "Bóg się rodzi". Na płycie znalazło się kilka utworów doskonale znanych z filmowych płyt Bregovicia takich jak: Underground, Arizona Dream, Królowa Margot i Czas cyganów. Nie mogło zabraknąć również jego słynnej cygańskiej orkiestry weselno-pogrzebowej. Z polskich muzyków pojawił się pięcioosobowy góralski zespół wokalny z Zakopanego (obecny Zakopower).
Marek Kościkiewicz, teraz już nie tylko właściciel małego Zic-Zaca, ale szef polskiego przedstawicielstwa wielkiego międzynarodowego koncernu BMG Ariola, wpadł na pomysł wspólnego album Kayah i Gorana Bregovića. Kayah początkowo nie była zainteresowana propozycją. Przygotowywała swój trzeci album i pielęgnowała życie osobiste. Wyszła za mąż za holenderskiego realizatora telewizyjnego Rinke Rooijensa i spodziewała się dziecka. W końcu przystąpiono jednak do pracy nad płytą. Wszyscy zainteresowani chcieli, by prace zakończono przed narodzinami dziecka, jednak przyjście na świat Rocha 1 grudnia 1998 roku przerwało realizację. Do pracy przystąpiono w dość trudnych warunkach. Kayah co pół godziny musiała wybiegać ze studia, by karmić dziecko. Płyta trafiła na rynek ponad cztery miesiące po jego narodzinach.
Single "Śpij kochanie, śpij" i "Prawy do lewego" podbiły Polskę, zostając jednymi z największych przebojów roku. Radiostacje ponownie przyznały wokalistce dwa Playboxy w jednym roku, w kategorii "Złota Dziesiątka". Na fali sukcesu albumu w roku 1999 wznowiono anglojęzyczną wersję jej pierwszego albumu. Potwierdzeniem oszałamiającej popularności projektu Kayah/Bregović był wrześniowy koncert obu artystów na warszawskim Służewcu, na który przyszło ponad 50 tysięcy osób. W związku z ogromną popularnością albumu w Polsce koncern Bertelsmanna postanowił promować płytę również za granicą. Płyta ukazała się w 11 krajach europejskich, m.in. we Włoszech, Hiszpanii, Francji, Turcji, Grecji, Izraelu, Czechach, Słowenii i Chorwacji. We Włoszech album ten w pierwszych dwóch tygodniach sprzedaży uplasował się na 7. miejscu na liście bestsellerów. Promocja płyty wiązała się z wyjazdem na press-tour do Włoch, a w następnej kolejności do Francji.
Album otrzymał Fryderyka jako najlepszy w 1999 roku, teledysk "Prawy do lewego" został wideoklipem roku, a Kayah dostała Fryderyka '99 w kategorii wokalistka roku. Artystka została również nagrodzona licznymi nagrodami, o których decydowała publiczność, na czele z Superjedynkami na Festiwalu Piosenki Polskiej w Opolu, gdzie w 2000 roku odebrała 4 statuetki w kategoriach: Najlepsza wokalistka, Przebój roku za"Śpij kochanie, śpij". Najlepsza płyta za "Kayah/Bregović" oraz Najlepszy teledysk za "Prawy do lewego".
