In this paper, we study a new privacy risk, namely DNS-based Fingerprints, introduced by passively collected DNS traffic. We intend to derive behavioral fingerprints from DNS traces, where each behavioral fingerprint targets at uniquely identifying its corresponding user and being immune to the change of time. The derived fingerprints have strong privacy implications such as de-anonymizing the DNS traces and tracking users’ locations across different networks. We have proposed a set of new patterns, which collectively form behavioral fingerprints by characterizing a user's DNS activities through three different perspectives including the domain name, the inter-domain relationship, and domains’ temporal behavior. We have performed extensive evaluation based on a large volume of DNS queries collected from a large campus network across three weeks. The experimental results have demonstrated that the proposed DNS-based fingerprints can accomplish high accuracy on revealing network users’ presence in a new DNS stream based on their fingerprint patterns derived from a historical DNS stream. We also experimentally explored the correlation between users’ general network activities and their DNS-based fingerprints.