Lestaluhu was born to Abdul Latif Lestaluhu and Healthy Ohorella as the first child of eight.
Lestaluhu lahir dari pasangan Abdul Latif Lestaluhu dan Sehat Ohorella sebagai anak pertama dari delapan bersaudara.