Cilmi nació en Dandenong, Melbourne, hija de inmigrantes italianos de origen arbëreshë.