A method and system are provided for causality analysis of Operating System-level (OS-level) events in heterogeneous enterprise hosts. The method includes storing, by the processor, the OS-level events in a priority queue in a prioritized order based on priority scores determined from event rareness scores and event fanout scores for the OS-level events. The method includes processing, by the processor, the OS-level events stored in the priority queue in the prioritized order to provide a set of potentially anomalous ones of the OS-level events within a set amount of time. The method includes generating, by the processor, a dependency graph showing causal dependencies of at least the set of potentially anomalous ones of the OS-level events, based on results of the causality dependency analysis. The method includes initiating, by the processor, an action to improve a functioning of the hosts responsive to the dependency graph or information derived therefrom.