Context-aware applications have been gaining huge interest in the last few years. With cell phones becoming ubiquitous computing devices, cell phone localization has become an important research problem. In this paper, we present Cell Sense, which is a probabilistic received signal strength indicator (RSSI)-based fingerprinting location determination system for Global System for Mobile Communications (GSM) phones. We discuss the challenges of implementing a probabilistic fingerprinting localization technique in GSM networks and present the details of the Cell Sense system and how it addresses these challenges. The proposed system using a hybrid technique that combines probabilistic and deterministic estimations to achieve both high accuracy and low computational overhead. Moreover, the accuracy of the hybrid technique is robust to changes in its parameter values. To evaluate our proposed system, we implemented Cell Sense on Android-based phones. Results from two different test beds, representing urban and rural environments, for three different cellular provider’s show that Cell Sense provides at least 108.57% enhancement in accuracy in rural areas and at least 89.03% in urban areas compared with current state-of-the-art RSSI-based GSM localization systems. In additional, the proposed hybrid technique provides more than 6 and 5.4 times reduction in computational requirements compared with state-of-the-art RSSI-based GSM localization systems for rural and urban test-beds, respectively. We also evaluate the effect of changing the different system parameters on the accuracy–complexity trade-off and how the cell tower and fingerprint densities affect system performance.