This paper develops low-complexity adaptive receivers for space-time block-coded (STBC) transmissions over frequency-selective fading channels. The receivers are useful for equalization purposes for single user transmissions and for joint equalization and interference cancellation for multiuser transmissions. The receivers exploit the rich code structure of STBC codes in order to deliver recursive-least-squares (RLS) performance at least-mean-squares (LMS) complexity. Besides reduced complexity, the proposed adaptive receivers also lower system overhead requirements.