Paraphrase plays an important role in various Natural Language Processing (NLP) problems, such as question answering, information retrieval, conversation systems, etc. Previous approaches mainly concentrate on producing paraphrases with similar semantics, namely fidelity, while recent ones begin to focus on the diversity of generated paraphrases. However, most of the existing models fail to explicitly emphasize on both metrics above. To fill this gap, we propose a submodular optimization-based VAE-transformer model to generate more consistent and diverse phrases. Through extensive experiments on datasets like Quora and Twitter, we demonstrate that our proposed model outperforms state-of-the-art baselines on BLEU, METEOR, TERp and n-distinct grams. Furthermore, through ablation study, our results suggest that incorporating VAE and submodularity functions could effectively promote fidelity and diversity respectively.