The instant invention provides binding proteins (“CD38-binding proteins”) which each comprise (1) a CD38-binding region for cell-targeting and (2) a Shiga toxin A Subunit effector polypeptide (“Shiga toxin effector polypeptide”). The Shiga toxin effector polypeptide components of the CD38-binding proteins may comprise a combination of mutations relative to a wild-type Shiga toxin sequence providing (1) de-immunization and/or (2) a reduction in protease sensitivity; wherein each Shiga toxin effector polypeptide retains one or more Shiga toxin function, such as, e.g., stimulating cellular internalization, directing intracellular routing, catalytic activity, and/or potent cytotoxicity. The CD38-binding proteins may have one or multiple uses, e.g., the selective killing of a specific CD38-expressing cell-type; and more generally, for the diagnosis and treatment of cancers and disorders involving CD38-expressing cells, e.g., in CD38-positive hematopoietic cancers such as multiple myeloma.