In this paper we have derived EM algorithms for MLSE over random channels. This new approach produces optimal estimates of the transmitted symbols by marginalizing over the random channel coefficient distribution. Simulation results demonstrate a BER performance improvement when using our EM algorithms.