With the wide spread usage of LBS, convenience has reached on the finger tips of mobile users, but on the other side, it has escalated many security and privacy concerns. In this paper we address the location K-anonymity problem using fuzzy spatio-temporal attributes, a new perspective of looking at privacy issue in location privacy. In the context of LBSs and mobile clients, location K-anonymity refers to K-anonymous usage of location information. A novel approach for determining location disclosure based on fuzzy attributes of spatio-temporal context is proposed which in turn will give us a value of K for K-anonymity purpose. Spatio-temporal fuzzy attributes for privacy issues are identified and Fuzzy Inference System (FIS) is implemented that takes these attributes as input and generates location disclosure value. Using Location disclosure value, K is computed for K-anonymity to ensure privacy. This value of K is directly based on current spatio temporal context and is valid for all users present in that context. Further, an exhaustive rule base of fuzzy rules is generated based on responses obtained by conducting survey on the potential users who frequently use POI (Point of Interest) services. Later on, fuzzy rules for FIS rule base are extracted using Fuzzy C Means (FCM) clustering technique. Using the rules extracted through FCM, the size of rule base is reduced and the performance of the FIS is evaluated. Number of rules in rule base is decreased for scalability and efficiency purposes. Root Mean Square Error (RMSE) for every reduced set is computed and compared with initial exhaustive rule base. It is observed that size of rule base can be decreased to a considerable extent. © 2014 IEEE.