From wikipedia, given any matrix $A$, we can sometimes decompose $A = LU$ using Gaussian elimination. Other times, a permutation matrix is needed, giving $PA = LU$.
If $A$ is Hermitian positive-definite, I can show that IF no permutation matrix is needed, then Gaussian elimination gives $A=LU$ which I can eventually massage and get the Cholesky decomposition $A=LL^*$. However, it seems that Hermitian positive-definite matrices are special in that no permutaiton matrix is ever needed, and hence the Cholesky decomposition always exist. Why?
The diagonal entries of $U$ in $A=LU$ are quotients of successive main diagonal minors of the matrix $A$. If $A$ is positive definite, the main minors are all positive. Sometimes this is called the Hurwitz criterion.
Put the diagonal elements of $U$ into a diagonal matrix $D$, then $A=LU=LDL^*$. Which again shows that the Cholesky decomposition works, since the critical numbers of the algorithm are these diagonal entries.