Before A GPS an Inertial Navigation System was used (to anyone who may know, please add to this as you are able).
from the Sept/Oct issue of PCPilot in the article Altitude Concorde by Andrew Whittaker.
An INS consists of a series of Gyroscopes primed on the ground and was used for crossing large expanses of water beyond the range of VOR stations. To prime the system, the pilot would enter the Latitude and Longitude of the plane at the gate. Once the gyroscopes are aligned and calibrated, they would detect the movement of the plane through all axis and translate them to updated Lat./Long. readings.
These days, trans-atlantic flights use an Inertial Reference System with laser gyroscopes as a backup to posititional data from GPS receivers.
The cost of replacing the archaic INS system with an FMC and GPS was just one of the reasons Air France and British Airways deemed the refurbishing the planes too expensive and decommissioned them.
I have heard that a plane, while calibrating, could not be moved for a certain period of time, or the data would be incorrect. I have also heard speculation that that is what happened with KAL 007 (that the then-USSR shot down in 1983), the plane was so far off-course because it was moved too soon.
For anyone who may not remember (or was too young to remember),
This article may tell you a bit about this mystery.
My first flight in a 172 on August 20, 2004

Doing the right thing is more important than doing the thing right. (P. Drucker)
When all think alike, then no one i