Having had a long-standing interest in art and history, Coate took to designing mazes and completed over 50 new mazes in Britain and around the world. Coate's maze designs are particularly noted for their symbolism. Although it is rarely possible to see a large maze in plan view, Coate's designs would often incorporate hidden shapes and references of significance to the clients who had commissioned the maze. Coate's first maze commission, The Imprint of Man, was completed in 1975 for a private garden at Lechlade Mill in Gloucestershire. The overall outline was of a giant footprint 57 m long by 29 m wide — a size calculated to match the size of a 300-m tall person, matching the height of the Eiffel Tower. The hedge maze, constructed from 3,000 yew bushes, ended up too large for its intended field. Coate's solution was to extend the maze into the adjacent river, creating an artificial island for the second toe. The intricate design incorporated 132 symbols, including numbers, signs of the zodiac and animals, birds and fishes. Some of his other notable mazes include;
Pyramid — yew hedge maze in the form of a pyramid at the Château de Belœil, Belgium, in which the height of the hedges increases to reach 6 m at the centre
Creation — yew hedge maze at Värmlands Säby, Sweden, for the Baroness of Falkenberg, with overlapping layers of symbolism. Seen one way, the egg-shaped outline represents the Garden of Eden incorporating figures for Adam, Eve, the Serpent and the apple. Seen another way, the hedge outlines form the shape of the horned Minotaur of the original Minoanlabyrinth.
In 1979, Coate was introduced to Adrian Fisher, another enthusiastic maze designer. Shortly afterwards Coate and Fisher formed the maze design company Minotaur Designs and designed 15 mazes together between 1979 and 1989,. These included:
Bath Festival Maze — a stone path in Beazer Gardens near the Pulteney Bridge, Bath, England, celebrating the city of Bath with motifs based on Georgian fanlights, arches from Isambard Kingdom Brunel's railway and a Roman-inspired mosaic circle at its centre
Marlborough Maze — a yew hedge maze at Blenheim Palace for the Duke of Marlborough and based on a stone carving by Grinling Gibbons representing the "Panoply of Victory", with a symbolism based on cannons, banners and trumpets.
El laberinto de Borges — San Rafael, Mendoza, Argentina, box hedge maze, measuring 95 m by 65 m, in memory of the writer Jorge Luis Borges, inspired by his short story "El Jardín de senderos que se bifurcan". Shaped like an open book, the design incorporates, in Braille, a quotation from the blind writer, that a book and a labyrinth are "one and the same".
The same design of the Borges Memorial Maze was used to build another one in the city of Venice in 2011, near the basilica of San Marcos, at San Giorgio Magiore´s gardens
