The Nautical Almanac Office (NAO) was established as a separate institution by Stratford who had been appointed Superintendent in 1831. The Office started some time between late 1831 and early 1832, however the actual date is not recorded.
The Office was at 3 Verulam Buildings, Gray's Inn, London, with permanent staff, under the auspices of the Admiralty (who had taken over from the Board of Longitude). William Dunkin, one of the experienced computers, moved from Truro, Cornwall, to Camden Town in order to join the staff of the Office.
The Almanac for 1834 was the first to contain more data for astronomers. It incorporated considerable improvements in its contents and presentation. Stafford's obituary  records
Under his Superintendence the recommendations of that Committee [RAS] were ably carried out, the character of the Almanac as a work of science was greatly raised, its magnitude and circulation, and its public usefulness, was greatly increased.
The first relocation of the office took place in 1832 when it moved to Somerset House, but returned to 3 Verulam Buildings, Gray's Inn, 10 years later, in 1842, where it remained until 1917.