This thesis offers a probabilistic solution to robust estimation using a novel adaptive estimator. Reliable state estimation is a mandatory prerequisite for autonomous systems interacting with the real world. The presence of outliers challenges the Gaussian assumption of numerous estimation algorithms, resulting in a potentially skewed estimate that compromises reliability. Many approaches attempt to mitigate erroneous measurements by using a robust loss function – which often comes with a trade-off between robustness and numerical stability. The proposed approach is purely probabilistic and enables adaptive large-scale estimation with non-Gaussian error models. The introduced Adaptive Mixture algorithm combines a nonlinear least squares backend with Gaussian mixtures as the measurement error model. Factor graphs as graphical representations allow an efficient and flexible application to real-world problems, such as simultaneous localization and mapping or satellite navigation. The proposed algorithms are constructed using an approximate expectation-maximization approach, which justifies their design probabilistically. This expectation-maximization is further generalized to enable adaptive estimation with arbitrary probabilistic models. Evaluating the proposed Adaptive Mixture algorithm in simulated and real-world scenarios demonstrates its versatility and robustness. A synthetic range-based localization shows that it provides reliable estimation results, even under extreme outlier ratios. Real-world satellite navigation experiments prove its robustness in harsh urban environments. The evaluation on indoor simultaneous localization and mapping datasets extends these results to typical robotic use cases. The proposed adaptive estimator provides robust and reliable estimation under various instances of non-Gaussian measurement errors.