Andrade was born in Salto in 1901 to an Argentine mother. José Ignacio Andrade, who is said to have been his father, is listed on his birth certificate as a witness. The elder Andrade, who was 98 years old when José Leandro Andrade was born, was an expert in African magic and is said to be an African-born slave who escaped from Brazil. At an early age, Andrade went to live with his aunt in a slum in Montevideo.