Kebede va néixer el 3 de gener de 1978 a Addis Abeba, Etiòpia,^[1] indret on va créixer.^[2] Un director de cinema la va veure mentre ella assistia al Liceu Guébré-Mariam i li va presentar a un agent de models francesos. Després d'acabar els seus estudis, es va traslladar a França per continuar els treballs a través d'una agència parisenca. Kebede més tard es va traslladar a Ciutat de Nova York. En alguna ocasió ha comentat que la indústria del modelatge a Etiòpia és molt diferent al de les passarel·les en la que es troba actualment, ja que a Etiòpia per a cada desfilada li van haver de proporcionar sabates.

Kebede es casà l'any 2000 amb el gestor de fons d'inversió etíop Kassy Kebede.^[2] Tingueren dues criatures: el fill Suhul (2001) i la filla Raee (2005).^[3] Des de 2007, resideix en família a Ciutat de Nova York.