The term physical accessibility has long been used by geographers, economists, and urban planners and reflects the relative ease of access to/from several urban/rural services by considering the traveling costs. Numerous accessibility measures, ranging from simple to sophisticated, can be observed in the geographical information systems (GIS)-based accessibility modeling literature. However, these measures are generally calculated from a constant catchment boundary (a most likely or average catchment boundary) based on constant deterministic transportation costs. This is one of the fundamental shortcomings of the current GIS-based accessibility modeling and creates uncertainty about the accuracy and reliability of the accessibility measures, especially when highly variable speeds in road segments are considered. The development of a new stochastic approach by using global positioning system (GPS)-based floating car data and Monte Carlo simulation (MCS) technique could enable handling the variations in transportation costs in a probabilistic manner and help to consider all possible catchment boundaries, instead of one average catchment boundary, in accessibility modeling process. Therefore, this article proposes a stochastic methodology for GIS-based accessibility modeling by using GPS-based floating car data and MCS technique. The proposed methodology is illustrated with a case study on medical emergency service accessibility in Eskisehir, Turkey. Moreover, deterministic and stochastic accessibility models are compared to demonstrate the differences between the models. The proposed model could provide better decision support for the decision-makers who are supposed to deal with accessibility, location/allocation, and service/catchment area related issues.