Summary: We introduce and study two natural generalizations of the Connected Vertex Cover (VC) problem: the \(p\)-Edge-Connected and \(p\)-Vertex-Connected VC problem (where \(p \geq 2\) is a fixed integer). We obtain an \(2^{\mathcal{O} ( p k )} n^{\mathcal{O} ( 1 )} \)-time algorithm for \(p\)-Edge-Connected VC and an \(2^{\mathcal{O} ( k^2 )} n^{\mathcal{O} ( 1 )} \)-time algorithm for \(p\)-Vertex-Connected VC. Thus, like Connected VC, both constrained VC problems are FPT. Furthermore, like Connected VC, neither problem admits a polynomial kernel unless NP \(\subseteq\) coNP/poly, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. Finally, we describe a \(2(p + 1)\)-approximation algorithm for the \(p\)-Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning \(p\)-vertex/edge-connected subgraphs of a \(p\)-vertex/edge-connected graph by Nishizeki and Poljak (1994) [30] and Nagamochi and Ibaraki (1992) [27].