The present invention relates to Shiga toxin A Subunit derived polypeptides and cell-targeting molecules comprising amino acid substitutions which equip the polypeptides with 1) de-immunization; 2) reduced, protease-cleavage sensitivity; and/or 3) a heterologous epitope cargo(s) while retaining Shiga toxin function(s), such as, e.g., potent cytotoxicity. Certain polypeptides of the invention exhibit reduced immunogenic potential in mammals and/or are capable of delivering an epitope to an MHC class molecule of a cell in which the polypeptide is present. Certain molecules comprising a polypeptide of the invention are well-tolerated by mammals while retaining one or more of the features mentioned above. The Shiga toxin polypeptides of the invention have uses as components of cell-targeting molecules for selectively killing specific cells; for selectively delivering cargos to specific cells, and as therapeutic and/or diagnostic molecules for treating and diagnosing a variety of conditions, including cancers, immune disorders, and microbial infections.