In 1675 the Royal Observatory was founded for the purpose of 'the certifying of the tables of the motions of the heavens and the places of the fixed stars, so as to find the so much desired longitude of places for the perfecting of the arts of navigation'. One of the major fruits of this work was the 'Nautical Almanac'.

The Almanac emerged out of attempts to determine longitude by means of lunar distance. The lunar method involved the calculation of the Moon's position relative to other celestial bodies at a specific time and place. This figure would be compared with the time at which the Moon would be in this position at Greenwich, and the difference between the Greenwich and local time used to calculate the longitude.

The fifth Astronomer Royal, Nevil Maskelyne (1732-1811), experimented with the lunar distance method during his voyage to observe the transit of Venus at St Helena in 1761. His results lead him to publish 'The British Mariner's Guide' in 1763, which included instructions for finding longitude at sea by lunar distance. In February 1765 he submitted a report to the Board of Longitude suggesting that an annual ephemeris be published. Following parliamentary approval, Maskelyne published the first edition of the 'Nautical Almanac' in 1766. The Almanac contained tables of the distances of the Moon from the Sun and bright stars for every three hours for the year 1767, and was the first publication of its type suitable for use at sea. Maskelyne also published a second volume containing permanent tables and other requisite information.

The publication of the 'Nautical Almanac' had a considerable impact and gave rise to the production of other almanacs and sets of lunar tables. Maskelyne continued to supervise its compilation, but the calculations were carried out by piece workers operating from home. The contents of the Almanac remained largely unchanged over the course of this period, although minor changes and additions were made from time to time.

In 1818 responsibility for the Almanac passed to Thomas Young (1773-1829), the holder of the new post of Superintendent, who reported to the Board of Longitude. Young was succeeded in 1829 by the Astronomer Royal, John Pond (1767-1836), who was followed in 1831 by William Samuel Stratford (1789-1853). In 1832 Stratford set up the Nautical Almanac Office to oversee the production of the Almanac, with the Superintendent now reporting to the Admiralty. Stratford introduced changes for the 1834 edition, the most significant being the use of Greenwich Mean Time in place of apparent time.

The next superintendent was John Russell Hind (1823-1895). He held the post from 1853 to 1891, but did not instigate any major changes. His successor, Arthur Matthew Weld Downing (1850-1917), introduced improvements recommended by the Paris Conference of 1896. During this period the prefix 'H.M.' was added to the title of the Almanac, first appearing in the edition for 1907, which was published in 1904.

Downing was succeeded in 1910 by Philip Herbert Cowell (1870-1949), who had been Chief Assistant at the Royal Observatory. He was an authority on celestial mechanics and wanted to turn the N.A.O. into a centre for dynamic astronomy, although the Admiralty disliked this idea. Cowell reverted to the original method of using computers working at home on 'piece-work' and reduced the number of established staff. He was responsible for the introduction of a Burroughs Adding Machine, and also added a Hollerith Tabulating Machine with punches and sorters.

Cowell was succeeded in 1930 by Leslie John Comrie (1893-1950). Comrie was responsible for changes which revolutionised and improved the 'Nautical Almanac'. He introduced calculating machines in place of logarithm tables and employed commercial card readers for scientific computing. He also added explanatory materials and tables into the Almanac and started a series of volumes on planetary coordinates. However, the Admiralty criticised Comrie for failing to consult properly before introducing these changes, and he was suspended in 1936.

Comrie was replaced with Donald Harry Sadler (1908-1987), who had previously been his deputy. Sadler continued the expansion of the N.A.O.'s work. The first edition of the 'Air Almanac' was published for the period October - December 1937, and a further volume of planetary coordinates was issued in 1939. In 1941 a series of astronomical navigation tables was published, the first since those published by Maskelyne in 1766. A major change took place in 1937, when the Royal Observatory assumed responsibility for the N.A.O. Sadler reported to the Astronomer Royal until 1965, when the Science Research Council assumed this role.

Sadler was succeeded by G.A. Wilkins (1970-1989), then B.D. Yallop (1989-1996). Thereafter, the post of Superintendent changed to Head of the H.M. Nautical Almanac Office. So far there have been two holders of this position: A.T. Sinclair (from 1996 to 1998) and P.T. Wallace (from 1998).

During the twentieth century the location of the Nautical Almanac Office shifted several times. It transferred with the Royal Observatory to Herstmonceux, in Sussex, in 1948, and followed the Observatory to Cambridge in 1980. When the R.G.O. closed in 1998, the N.A.O. settled at the Rutherford Appleton Laboratory, near Abingdon, Oxfordshire.