Część instrumentalna utworu składa się z cimpoi (rumuńskiej kobzy), saksofonu, perkusji, fletu i pianina.
Na początku 2012 roku piosenka osiągnęła sukces w Rumunii. Za namową fanów Mandinga zgłosiła ją do rumuńskich preselekcji do Konkursu Piosenki Eurowizji "Selecția Națională 2012". Utwór przeszedł eliminacje i dostała się do finałowej piątnastki kandydatów. 10 marca odbył się finał selekcji, w których Mandinga wykonała swój utwór jako dziesiąty uczestnik. Po zakończeniu głosowania ogłoszono, że Mandinga zdobyła ponad 7,000 głosów od widzów, co przełożyło się na 12 punktów w televotingu. Jurorzy przyznali piosence 85 punktów, co dało zespołowi kolejne 10 punktów. Ostatecznie zdobyli 22 punkty, co oznaczało, że Mandinga z "Zaleilah" została reprezentantem Rumunii podczas Konkursu Piosenki Eurowizji 2012.
22 maja odbył się pierwszy półfinał konkursu, w którym "Zaleilah" została wykonana jako szósta propozycja konkursowa. Zdobyła 120 punktów, co przełożyło się na 3. miejsce i awans do finału. Piosenka zajęła ostatecznie 12. miejsce w finale konkursu, który odbył się 26 maja.