Summary: In many mobile robot applications, the high cost of damaging the robot or its environment makes even rare failures unacceptable. To mitigate this risk, a robot must be able to detect potentially hazardous situations before it experiences a major failure. This problem therefore becomes one of novelty and change detection: how a robot can identify when perception inputs differ from prior inputs seen during training or previous operation in the same area. With this ability, the system can either avoid novel locations to minimize risk or stop and enlist human help via supervisory control or teleoperation. We present an anytime novelty detection algorithm that deals with noisy and redundant high-dimensional feature spaces that are common in robotics by utilizing prior class information within the training set. This approach is also well suited for online use when a constantly adjusting environmental model is beneficial. Furthermore, we address the problem of change detection in an environment of repeated operation by framing it as a location-specific version of novelty detection and present an online scene segmentation algorithm that improves accuracy across diverse environments. We validate these approaches through extensive experiments onboard two outdoor mobile robot platforms, show that our approaches are robust to noisy sensor data and moderate registration errors, and argue how such abilities could be key in increasing the real-world applications and impact of mobile robotics.