A computer-implemented method for detecting data-stealing malware may include: 1) detecting an attempt by an untrusted application to access a storage location that is known to be used by a legitimate application when storing potentially sensitive information, 2) determining that the legitimate application is not installed on the computing device, 3) determining that the untrusted application represents a potential security risk, and then 4) performing a security operation on the untrusted application. Corresponding systems and computer-readable instructions embodied on computer-readable media are also disclosed.