Botnets are recognized as one of the most dangerous threats to the Internet infrastructure. They are used for malicious activities such as launching distributed denial of service attacks, sending spam, and leaking personal information. Existing botnet detection Methods produce a number of good ideas, but they are far from complete yet, since most of them cannot detect botnets in an early stage of their lifecycle; moreover, they depend on a particular command and control (C&C) protocol. In this paper, we address these issues and propose an Online unsupervised Method, called BotOnus, for botnet detection that does not require a priori knowledge of botnets. It extracts a set of flow feature vectors from the network traffic at the end of each time period, and then groups them to some flow clusters by a novel Online fixed-width clustering algorithm. Flow clusters that have at least two members, and their intra-cluster similarity is above a similarity threshold, are identified as suspicious botnet clusters, and all hosts in such clusters are identi ed as bot infected. We demonstrate the effectiveness of BotOnus to detect various botnets including HTTP-, IRC-, and P2P-based botnets using a testbed network. The results of experiments show that it can successfully detect various botnets with an average detection rate of 94: 33% and an average false alarm rate of 3: 74%.