Computational protein docking is a useful technique for gaining insights into protein interactions. We have developed an algorithm M-ZDOCK for predicting the structure of cyclically symmetric (Cn) multimers based on the structure of an unbound (or partially bound) monomer. Using a grid-based Fast Fourier Transform approach, a space of exclusively symmetric multimers is searched for the best structure. This leads to improvements both in accuracy and running time over the alternative, which is to run a binary docking program ZDOCK and filter the results for near-symmetry. The accuracy is improved because fewer false positives are considered in the search, thus hits are not as easily overlooked. By searching four instead of six degrees of freedom, the required amount of computation is reduced. This program has been tested on several known multimer complexes from the Protein DataBank, including four unbound multimers: three trimers and a pentamer. For all of these cases, M-ZDOCK was able to find at least one hit, whereas only two of the four testcases had hits when using ZDOCK and a symmetry filter. In addition, the running times are 30-40% faster for M-ZDOCK.