We propose several differential decoding schemes for asynchronous multi-user MIMO systems based on orthogonal space-time block codes (OSTBCs) where neither the transmitters nor the receiver has knowledge of the channel. First, we derive novel low complexity differential decoders by performing interference cancelation in time and employing different decoding methods. The decoding complexity of these schemes grows linearly with the number of users. We then present additional differential decoding schemes that perform significantly better than our low complexity decoders and outperform the existing synchronous differential schemes but require higher decoding complexity compared to our low complexity decoders. The proposed schemes work for any square OSTBC, any constant amplitude constellation, any number of users, and any number of receive antennas. Furthermore, we analyze the diversity of the proposed schemes and derive conditions under which our schemes provide full diversity. For the cases of two and four transmit antennas, we provide examples of PSK constellations to achieve full diversity. Simulation results show that our differential schemes provide good performance. To the best of our knowledge, the proposed differential detection schemes are the first differential schemes for asynchronous multi-user systems.