Traversability illustrates the difficulty of driving through a specific region and encompasses the suitability of the terrain for traverse based on its physical properties, such as slope and roughness, surface condition, etc. In this survey we highlight the merits and limitations of all the major steps in the evolution of traversability estimation techniques, covering both non-trainable and machine-learning methods, leading up to the recent proliferation of deep learning literature. We discuss how the nascence of Deep Learning has created an opportunity for radical improvement in traversability estimation. Finally, we discuss how self-supervised learning can help satisfy deep methods' increased need for (challenging to acquire and label) large-scale datasets.