This thesis explores how can network traffic analysis be used for accurate and efficient detection of malware network activities. The thesis focuses on botnet detection by devising novel detection approaches that are aimed at identifying malware network activity at different points in the network and based on different, mutually complementary, principles of traffic analysis. The proposed approaches rely on machine learning algorithms (MLAs) for automated and resource-efficient identification of the patterns of malicious network traffic. We evaluated the proposed methods through extensive evaluations using traffic traces from honeypots and malware testing environments as well as operational ISP networks. Based on the evaluation, the novel detection methods provide accurate and efficient identification of malicious network traffic, thus being promising in the light of operational deployment. Furthermore, the thesis provides an overview of some of the biggest challenges of using MLAs for identifying malicious network activities. The challenge specially addressed by the thesis is the “ground truth” problem, where we proposed a novel labeling approach for obtaining the ground truth on agile DNS traffic that provides reliable and time-efficient labeling. Finally, the thesis outlines the opportunities for future work on realizing robust and effective detection solutions.