Advanced technology has recently provided truly immersive virtual environments with teleoperated robotic devices. In order to control movements from a distance, the human sensorimotor system has to overcome the effects of delay. Currently, little is known about the mechanisms that underlie haptic estimation in delayed environments. The aim of this research is to explore the effect of a delay on perception of surfaces stiffness. We used a forced choice paradigm in which subjects were asked to identify the stiffer of two virtual spring-like surfaces based on manipulation without visual feedback. Virtual surfaces were obtained by generating an elastic force proportional to the penetration of the handle of a manipulandum inside a virtual boundary. In some cases, we introduced a delay between the displacement and the elastic force. We assume that for estimating stiffness, the brain relates the experienced interaction forces with the amount of penetration. The results of the experiment indicate a systematic dependence of the estimated stiffness upon the delay between position and force. When the force lagged the penetration, surfaces were perceived as stiffer. Conversely, when the force led the penetration, surfaces were perceived as softer. We compared the perceptual findings with different models. Our findings are equally consistent with stiffness estimates based either on a) local estimates of forces and positions sensed during the inward probing or b) estimate of maximum interaction force. Our findings are not consistent with an estimate of compliance derived from the net amount of motion inside the surface and with linear estimates of stiffness based on the entire force/motion history.