The use of cognitive radio technology for M2M communications is expected to be indispensable in near future. In the meanwhile, the unique features of M2M communications create various challenges, especially at the MAC layer. We aim to design a cognitive MAC protocol for generic M2M communications that sufficiently fulfils the service requirements of M2M devices. For this purpose, we propose PRMA, carry out its feasibility study, adapt, and significantly enhance it with modifications especially tailored for M2M communications. By combining PRMA and cognitive radio technology, a frame structure is developed for supporting co-existence of cognitive M2M network with the primary network. This frame structure is further optimized considering different tradeoffs. The proposed protocol is evaluated using both analytical and simulation results.