Function approximation from input and output data is one of the most investigated problems in signal processing. This problem has been tackled with various signal processing and machine learning methods. Although tensors have a rich history upon numerous disciplines, tensor-based estimation has recently become of particular interest in system identification. In this paper we focus on the problem of adaptive nonlinear system identification solved with interpolated tensor methods. We introduce three novel approaches where we combine the existing tensor-based estimation techniques with multidimensional linear interpolation. To keep the reduced complexity, we stick to the concept where the algorithms employ a Wiener or Hammerstein structure and the tensors are combined with the well-known LMS algorithm. The update of the tensor is based on a stochastic gradient decent concept. Moreover, an appropriate step size normalization for the update of the tensors and the LMS supports the convergence. Finally, in several experiments we show that the proposed algorithms almost always clearly outperform the state-of-the-art methods with lower or comparable complexity.