The paper presents a method for a malware’s signature generation based on API call tracing. Technique allows malware detection using a proposed form of signature. The main idea of proposed signature generation is a difference between frequency and interaction of a critical API calls performed by malicious program and benign applications in the process of their own execution. Accordingly the program's behavior signature based on API call tracing consists of two components: the call frequency and the nature of the interaction of critical API calls. An analysis of the first component allows determining the distribution of the critical API calls by groups concerning theirs malicious activity and displays the quantitative component of the signature. An analysis of the second component of the signature provides an opportunity to distinguish malware from benign applications not only in the presence of critical API calls, but also in their interaction with each other. The experimental results showed that the effectiveness of the malware detection using proposed signatures is up to 96.56%.