Клуб је основан 1922. године, а 1960. улази у Прву лигу Југославије. У сезони 1977/78. стиже до финала Купа победника купова где је поражен од Ференцвароша из Будимпеште, а у сезони 1985/86. осваја дуплу круну, освојивши куп и првенство Југославије. Клуб 2007. и 2008. осваја првенство Црне Горе, а 2009. национални куп. Највећи успех клуб остварује у сезони 2008/09. када осваја Евролигу, у финалу је победио италијански Про Реко са 8:7, а 2009. такође осваја и Суперкуп Европе.
У сезони 2009/10. били су вицешампиони Европе изгубивши у финалу од Про Река. 2021 године осваја куп Црне Горе.
Послије 16 година зауставља вјечитог ривала ПВК Јадран у побједничком низу освајања првенства Црне Горе у сезони 2023/24.
Навијачи
Навијачи ВПК Приморац су се организували у групу Бештије. Бештије су једне од најстаријих група навијача што се тиче ватерпола у Црној Гори. Основали су се 1986. године
