For finite-dimensional Hopf algebras, their classification in characteristic $0$ (e.g. over $mathbb{C}$) has been investigated for decades with many fruitful results, but their structures in positive characteristic have remained elusive. In this paper, working over an algebraically closed field $mathbf{k}$ of prime characteristic $p$, we introduce the concept, called Primitive Deformation, to provide a structured technique to classify certain finite-dimensional connected Hopf algebras which are almost primitively generated; that is, these connected Hopf algebras are $p^{n+1}$-dimensional, whose primitive spaces are abelian restricted Lie algebras of dimension $n$. We illustrate this technique for the case $n=2$. Together with our preceding results in arXiv:1309.0286, we provide a complete classification of $p^3$-dimensional connected Hopf algebras over $mathbf{k}$ of characteristic $p>2$.