In this paper, we develop a strong Milstein approximation scheme for solving stochastic delay differential equations (SDDE's). The scheme has convergence order 1. In order to establish the scheme, we prove an infinite-dimensional Itô formula for "tame" functions acting on the segment process of the solution of an SDDE. It is interesting to note that the presence of the memory in the SDDE requires the use of the Malliavin calculus and the anticipating stochastic analysis of Nualart and Pardoux. Given the non-anticipating nature of the SDDE, the use of anticipating calculus methods appears to be novel.