The emerging marketplace for online free services in which service providers (SPs) earn revenue from using consumer data in direct and indirect ways has led to significant privacy concerns. This begs understanding of the following question: is there a sustainable market for multiple SPs that offer privacy differentiated free services? This paper studies the impact of privacy on free online service markets by augmenting the classical Hotelling model for market segmentation analysis. A parametrized game-theoretic model is proposed which captures: (i) the fact that for the free service market, consumers value service not in monetized terms but by the quality of service (QoS); (ii) the differentiator of services is not product price but the privacy risk advertised by an SP; and (iii) consumer’s heterogeneous privacy preference for SPs. For the two-SP problem with uniformly distributed consumer privacy preference and linear SP profit function, the results suggest that: (i) when consumers place a higher value on privacy, it leads to a larger market share for the SP providing untargeted services and a “softened" competition between SPs; (ii) SPs offering high privacy risk services are sustainable only if they offer sufficiently high QoS; and (iii) SPs that are capable of differentiating on services that do not directly use consumer data gain larger market share. Similar results are observed when the consumer’s privacy preference is modeled as a truncated Gaussian distribution.