Cancer is a disease driven in part by alterations to key signaling pathways. However, our knowledge of these pathways remains incomplete.  We introduce Combinations of Mutually Exclusive Alterations (CoMEt), an algorithm to identify multiple combinations of alterations that exhibit a pattern of mutual exclusivity across individuals, a pattern often observed for alterations in the same pathway. CoMEt includes two key innovations. First is an exact statistical test for mutual exclusivity with a novel enumeration procedure for computing the corresponding tail probability. Second is a stochastic algorithm to perform simultaneous analysis of multiple sets of mutually exclusive and subtype-specific alterations. We demonstrate that CoMEt outperforms existing approaches on simulated and real data. We apply CoMEt to five different cancer types, identifying both known cancer genes and pathways, and novel putative cancer genes.