Simultaneous localization and mapping (SLAM) are essential in numerous robotics applications, such as autonomous navigation. Traditional SLAM approaches infer the metric state of the robot along with a metric mapof the environment. While existing algorithms exhibit good results, they are still sensitive to measurement noise,sensor quality, and data association and are still computationally expensive. Alternatively, some navigation andmapping missions can be achieved using only qualitative geometric information, an approach known as qualitativespatial reasoning (QSR). We contribute a novel probabilistic qualitative localization and mapping approach in thiswork. We infer both the qualitative map and the qualitative state of the camera poses (localization). For the firsttime, we also incorporate qualitative probabilistic constraints between camera poses (motion model), improvingcomputation time and performance. Furthermore, we take advantage of qualitative inference properties to achievevery fast approximated algorithms with good performance. In addition, we show how to propagate probabilisticinformation between nodes in the qualitative map, which improves estimation performance and enables inferenceof unseen map nodes - an important building block for qualitative active planning. We also conduct a study thatshows how well we can estimate unseen nodes. Our method particularly appeals to scenarios with few salientlandmarks and low-quality sensors. We evaluate our approach in simulation and on a real-world dataset and showits superior performance and low complexity compared to the state-of-the-art. Our analysis also indicates goodprospects for using qualitative navigation and planning in real-world scenarios.