The first written account of the phenomenon might be due to Eratosthenes (276-195 BC), the head of Alexandrian Museum and contemporary of Archimedes, with whom he corresponded. Eratosthenes is credited with proposing to use longitude and latitude to specify locations on Earth, an idea developed further by Hipparchus (190-120 BC), "the father of astronomy", and later used by Ptolemy in his maps. Hipparchus appears to be the first to suggest explicitly that local time determines longitude. Interestingly enough, Ctesibius (285–222 BC) invented the first fairly precise and constantly working clock, the clepsydra, around the same time.
However, it is likely that differences in local occurrences of astronomical events were noticed much earlier by seafarers. NOVA mentioned in their special that Phoenicians knew, possibly as far back as late second millenium BC, that "at any one time in the year at any one point on the globe, the sun and stars are found above the horizon at certain fixed "heights"—a distance that mariners can measure with as simple an instrument as one's fingers", and used it for navigation.
Unfortunately, there was little systematic development of navigational uses of local time until the 16-th century. In 1502 Amerigo Vespucci wrote "I maintain that I learned [my longitude]... by the eclipses and conjunctions of the Moon with the planets", and Johannes Werner developed the method systematically in his 1514 commentary to a translation of Ptolemy's Geography. Subsequent proposals for longitude determination based on astronomical observations were given by Galileo and Halley among others. However, the calculations involved were too complicated for regular use, and the issue came to be known as the problem of longitude. Spanish kings even offered a prize for solving it in 1567, and increased it in 1598. The idea of using chronometers, which ultimately resolved the longitude problem, is usually attributed to Gemma Frisius (1508-1555), but it gained little currency until Huygens built precise pendulum clocks in late 17th century.