Nommée d'après la High Road de Leytonstone, tronçon d'une ancienne route d'Epping à Londres.
Leytonstone, d'abord attesté sous la forme Leyton-atte-Stone, c'est Leyton – l'établissement sur la rivière Lea – près de la High Stone, traditionnellement décrite comme une borne milliaire romaine. La station ouvrit en 1894 sous le simple nom de Leytonstone et fut rebaptisée Leytonstone High Road en 1949 ; la station Leytonstone de la Central line se trouve à dix minutes à pied.