The invention relates to recombinant bovine leukemia viruses that have an attenuated phenotype and comprise a combination of at least two specific mutations. The invention also provides recombinant nucleic acids encoding such viruses, vectors comprising such nucleic acids, and host cells comprising such nucleic acids or vectors. The recombinant attenuated BLV viruses, recombinant nucleic acids, vectors and host cells allow for the preparation of improved vaccines, in particular vaccines suitable for the prophylactic treatment of BLV-associated diseases in subjects. The invention further provides methods for treating BLV-associated diseases in subjects and pharmaceutical compositions suitable for use in these methods.