In this paper, we propose a low complexity graph-based linear minimum mean-square-error (LMMSE) equalizer in order to remove inter-symbol and inter-stream interference in a multiple input multiple output (MIMO) communication. The proposed state space representation inflicted on the graph provides linearly increasing computational complexity with block length. In addition, owing to the Gaussian assumption used in the presented cycle-free factor graph, the complexity of the suggested equalizer structure is not affected by the size of the signaling space. In addition, we introduce an efficient way of computing extrinsic bit log-likelihood ratio values for the LMMSE estimation compatible with higher order alphabets, which is shown to perform better than the other methods in the literature. Overall, we provide an efficient receiver structure reaching high data rates in frequency selective MIMO systems, whose performance is shown to be very close to a genie-aided matched filter bound through extensive simulations.