This paper presents a probabilistic technique for identifying support surfaces like floors, walls, stairs, and rails from unstructured 3D point cloud scans. A Markov random field is employed to model the joint probability of point labels, which can take on a number of user-defined surface classes. The probability of a point depends on both local spatial features of the point cloud around the point as well as the classifications of points in its neighborhood. The training step estimates joint and pairwise potentials from labeled point cloud datasets, and the prediction step aims to maximize the joint probability of all labels using a hill-climbing procedure. The method is applied to stair and ladder detection from noisy and partial scans using three types of sensors: A sweeping laser sensor, time-offlight depth camera, and a Kinect depth camera. The resulting classifier achieves approximately 75% accuracy and is robust to variations in point density.