Recognizing human activity from a stream of sensory observations is important for a number of applications such as surveillance and human-computer interaction. Hidden Markov Models (HMMs) have been proposed as suitable tools for modeling the variations in the observations for the same action and for discriminating among different actions. HMMs have come in wide use for this task but the standard form suffers from several limitations. These include unrealistic models for the duration of a sub-event and not encoding interactions among multiple agents directly. Semi- Markov models and coupled HMMs have been proposed in previous work to handle these issues. We combine these two concepts into a coupled Hidden semi-Markov Model (CHSMM). CHSMMs pose huge computational complexity challenges. We present efficient algorithms for learning and decoding in such structures and demonstrate their utility by experiments with synthetic and real data.