Navigation has been one of the fundamental technology challenges for centuries. Astronomy in Europe had become an applied science largely focused on navigation in the 17th, 18th and first half of the 19th centuries as it was so linked to commerce. Inertial systems are temperamental, expensive and prone to accumulating error, but they became core to navigation after about 1950. All of this was hard.
There was a crazy scheme that involved orbiting clocks and triangulation - but it was the sort of thing that physicists put up on the chalkboard to discuss other interesting problems. The technical challenges would be enormous - you would be crazy to try as it would be silly expensive. But DARPA made a go of it and it worked. Oddly it is a technology that requires both special and general relatively. And now we have $20 chipsets that give accuracy anywhere on Earth to a couple of meters - soon a few billion phones will be able to tell you where you are (and perhaps inform others you may not want to know).
Nancy pointed to a blog post that shows some proto positioning systems. This one in a car is from 1932.
For the record I did some work on GPS denied navigation a few years ago - "how well can you do if the system was unavailable?" Things have progressed a bit since 1970, but the competing technologies are basically static and it is still enormously expensive and difficult.