A computer-implemented method for detecting malware may include (1) identifying a behavioral trace of a program, the behavioral trace including a sequence of runtime behaviors exhibited by the program, (2) dividing the behavioral trace to identify a plurality of n-grams within the behavioral trace, each runtime behavior within the sequence of runtime behaviors corresponding to an n-gram token, (3) analyzing the plurality of n-grams to generate a feature vector of the behavioral trace, and (4) classifying the program based at least in part on the feature vector of the behavioral trace to determine whether the program is malicious. Various other methods, systems, and computer-readable media are also disclosed.