Over the last 20 years, navigation has almost become synonymous with satellite positioning, e.g. the Global Positioning System (GPS). On land, sea or in the air, on the road or in a city, knowing ones position is a question of getting a clear line of sight to enough satellites. Unfortunately, since the signals are extremely weak there are environments the GPS signals cannot reach but where positioning is still highly sought after, such as indoors and underwater. Also, because the signals are so weak, GPS is vulnerable to jamming. This thesis is about alternative means of positioning for three scenarios where gps cannot be used. Indoors, there is a desire to accurately position first responders, police officers and soldiers. This could make their work both safer and more efficient. In this thesis an inertial navigation system using a foot mounted inertial magnetic mea- surement unit is studied. For such systems, zero velocity updates can be used to significantly reduce the drift in distance travelled. Unfortunately, the estimated direction one is moving in is also subject to drift, causing large positioning errors. We have therefore chosen to throughly study the key problem of robustly estimating heading indoors. To measure heading, magnetic field measurements can be used as a compass. Unfortunately, they are often disturbed indoors making them unreliable. For estimation support, the turn rate of the sensor can be measured by a gyro but such sensors often have bias problems. In this work, we present two different approaches to estimate heading despite these shortcomings. Our first system uses a Kalman filter bank that recursively estimates if the magnetic readings are disturbed or undisturbed. Our second approach estimates the entire history of headings at once, by matching integrated gyro measurements to a vector of magnetic heading measurements. Large scale experiments are used to evaluate both methods. When the heading estimation is incorporated into our positioning system, experiments show that positioning errors are reduced significantly. We also present a probabilistic stand still detection framework based on accelerometer and gyro measurements. The second and third problems studied are both maritime. Naval navigation systems are today heavily dependent on GPS. Since GPS is easily jammed, the vessels are vulnerable in critical situations. In this work we describe a radar based backup positioning system to be used in case of GPS failure. radar scans are matched using visual features to detect how the surroundings have changed, thereby describing how the vessel has moved. Finally, we study the problem of underwater positioning, an environment gps signals cannot reach. A sensor network can track vessels using acoustics and the magnetic disturbances they induce. But in order to do so, the sensors themselves first have to be accurately positioned. We present a system that positions the sensors using a friendly vessel with a known magnetic signature and trajectory. Simulations show that by studying the magnetic disturbances that the vessel produces, the location of each sensor can be accurately estimated.