Proximity-based services (PBS) are a subclass of location-based services that aim to detect the closest point of interest by comparing relative position of a mobile user with a set of entities to be detected. Traditionally, the performances of PBS are measured on the basis of the norm of the estimation error. Although this performance criterion is suitable for location-based services that aim tracking applications, it does not give enough information about the performance of PBS. This paper provides a novel framework quantifying the system performance of PBS by making use of spatially quantized decision regions that are determined according to service properties. The detection problem in PBS is modeled by an M-ary hypothesis test, and analytical expressions for correct detection, false alarm, and missed detection rates are derived. A relation between location estimation accuracy requirements that are mandated by regulatory organizations and the performance metrics of PBS is given. Additionally, a flexible cost expression that can be used to design high-performance PBS is provided. A system deployment scenario is considered to demonstrate the results. By using this framework, PBS designers can improve their command on the services' behavior and estimate service performance before deployment. Copyright (c) 2011 John Wiley & Sons, Ltd.