Topological maps are light-weight, graphical representations of environments that are scalable and amenable to symbolic manipulation. Thus, they are well- suited for basic robot navigation applications, and also provide a representational basis for the procedural and semantic information needed for higher-level robotic tasks. However, their widespread use has been impeded in part by the lack of reliable, general purpose algorithms for their construction. In this dissertation, I present a probabilistic framework for the construction of topological maps that addresses topological ambiguity, is failure-aware, computa- tionally efficient, and can incorporate information from various sensing modalities. The framework addresses the two major problems of topological mapping, namely topological ambiguity and landmark detection. The underlying idea behind overcoming topological ambiguity is that the com- putation of the Bayesian posterior distribution over the space of topologies is an effective means of quantifying this ambiguity, caused due to perceptual aliasing and environment variability. Since the space of topologies is combinatorial, the posterior on it cannot be computed exactly. Instead, I introduce the concept of Probabilistic Topological Maps (PTMs), a sample-based representation that ap- proximates the posterior distribution over topologies given the available sensor measurements. Sampling algorithms for the efficient computation of PTMs are described. The PTM framework can be used with a wide variety of landmark detection schemes under mild assumptions. As part of the evaluation, I describe a novel landmark detection technique that makes use of the notion of "surprise" in mea- surements that the robot obtains, the underlying assumption being that landmarks are places in the environment that generate surprising measurements. The com- putation of surprise in a Bayesian framework is described and applied to various sensing modalities for the computation of PTMs. The PTM framework is the first instance of a probabilistic technique for topo- logical mapping that is systematic and comprehensive. It is especially relevant for future robotic applications which will need a sparse representation capable of accomodating higher level semantic knowledge. Results from experiments in real environments demonstrate that the framework can accomodate diverse sensors such as camera rigs and laser scanners in addition to odometry. Finally, results are pre- sented using various landmark detection schemes besides the surprise-based one.