We cast the word alignment problem as maximizing a submodular function under matroid constraints. Our framework is able to express complex interactions among alignments while remaining computationally efficient, thanks to the power and generality of submodular functions. We show that submodularity naturally arises when modeling word fertility. Experiments on the English-French Hansards alignment task show that our approach achieves lower alignment error rates compared to conventional matching based approaches.