In this article, optimal control problems of differential equations with delays are investigated for which the associated Hamilton-Jacobi-Bellman (HJB) equations are nonlinear partial differential equations with delays. This type of HJB equation has not been previously studied and is difficult to solve because the state equations do not possess smoothing properties. We introduce a new notion of viscosity solutions and identify the value functional of the optimal control problems as the unique solution to the associated HJB equations. An analytical example is given as application.