This paper presents a state estimation approach for legged robots based on stochastic filtering. The key idea is to extract information from the kinematic constraints given through the intermittent contacts with the ground and to fuse this information with inertial measurements. To this end, we design an unscented Kalman filter based on a consistent formulation of the underlying stochastic model. To increase the robustness of the filter, an outliers rejection methodology is included into the update step. Furthermore, we present the nonlinear observability analysis of the system, where, by considering the special nature of 3D rotations, we obtain a relatively simple form of the corresponding observability matrix. This yields, that, except for the global position and the yaw angle, all states are in general observable. This also holds if only one foot is in contact with the ground. The presented filter is evaluated on a real quadruped robot trotting over an uneven and slippery terrain.