On the 9th day of February 1765 Maskelyne presented to the Board of Longitude his suggestion for the calculation and publication of a "Nautical Ephemeris", designated to make possible the determination of longitude at sea by means of the method of Lunar Distances. The Commissioners agreed that it would be helpful, but it was not until the meeting on 28th May that the Board appointed Maskelyne and the Professors to form a plan, which was produced in two days. The Commissioners resolved that Application should be made to Parliament - for power to give a Reward to persons to compile a Nautical Ephemeris and for Authority to print the same.
The application was duly approved and the first edition of The Nautical Almanac and Astronomical Ephemeris (NA & AE) was prepared for the year 1767 and published in 1766. Some 2,000 copies (price 2s 6d) were printed. At the same time Maskelyne also published his Tables Requisite to be Used with the Astronomical and Nautical Ephemeris to serve as a handbook for navigators using lunar distances. These Tables Requisite, were published from time to time, and it is said that the 1781 edition sold 10,000 copies immediately on publication.
In the last paragraph of the preface  to the first (1767) Almanac Maskelyne tells us about the process he setup and the quality control:
All the Articles of the Ephemeris were computed by Two separate Persons, and examined by a Third, except of the Moon's Longitude, Latitude, Right Ascension, Declination, Semidiameter, and parallax, which, for Noon, were computed by One Person, and for Midnight by another, and the Truth of these Calculations ascertained by means of Differences, which, for the Moon's Longitude, were carried out as far as the Fourth Order.
One of the first "computers" was the Reverend John Edwards. His hobby was astronomy and building telescopes and had been introduced to Maskelyne sometime during 1773 to 1774. Maskelyne subsequently employed him as a computerer. It is surprising that he had the time for all this computation, what with his preaching, teaching and carrying out experiments. Unfortunately he died, aged 36 years, having inhaled a lungful of arsenic fumes while trying to improve the reflectivity of his mirror. However, the computing of the Almanac allocated to him continued without interruption, as it had been his wife, Mary, who had been doing the work! Mary wrote to Maskelyne petitioning that she was struggling to make ends meet. So Maskelyne gave her more work. Eventually she was computing a whole year's worth of tables:
Mary's reputation for reliability and accuracy was her greatest asset. When the computers got too far ahead - with 10 years data in hand - the Board of Longitude stopped work. Mary asked for compensation for lost income and got it! 
Maskelyne took a very active role during the remainder of his life undertaking the superintendence of this invaluable annual publication. He not only had the calculations sent to him, which he then dispatched to the comparer, but he also dealt with the printers, supplying them with paper, and dealing with the publishers. During this time his team consisted of four computers who were responsible for more than half the computations, while another twenty-fours computers were responsible for the remainder. While three quarters of the comparisons were the work of the Reverand Malachy Hitchins. Altogether, over the period, there were ten comparers who also dealt with proof-reading the printer's copy.
It was necessary to produce the tables several years in advance as voyages of exploration often lasted for many years. This continued to be the practice in the 20th-century as the high-precision ephemerides were used in many countries for the preparation of navigational and local almanacs.