Consider an incomplete Cholesky factorization of a sparse symmetric positive definite matrix. It is common practice to start with a symmetric permutation of the rows and columns of the matrix using an ordering to reduce fill in the complete Cholesky factor. Such an approach has two drawbacks. First, such an ordering is designed to reduce fill or operation counts in the complete Cholesky factor, and thus does not necessarily address the issue of controlling fill or operation counts during incomplete factorization. Second, because the ordering is determined in advance of the incomplete factorization, it is not easy to accommodate alternative pivoting sequences, for example, using numeric measures to promote stability, while taking into account their impact on fill and operation counts. In this paper, we consider an alternative approach that interleaves ordering with numeric computation in an incomplete Cholesky factorization. Such an interleaved scheme controls fill and operation counts. It also allows the incorporation of some limited, pivot selection strategies for stability. We demonstrate through experiments that our interleaved minimum-degree approach leads to fewer failures during incomplete factorization and improved convergence when the incomplete factor is used as a preconditioner for the conjugate gradient method. We conjecture that the improvements in the quality of preconditioning arise from the ability of our method to generate better approximations to the complete factor.