In this paper, we propose a new auxiliary-vector (AV) algorithm using the conjugate orthogonality for speech enhancement. When only a limited data record is available, the AV algorithm is the state-of-the-art for obtaining the minimum-variance-distortionless (MVDR) filter. However, the current AV algorithms suffer from convergence problems when applied to the speech enhancement. Based on the conjugate Gram-Schmidt process, we develop new auxiliary vectors that are conjugate orthogonal and apply them to the AV algorithm. The proposed conjugate AV algorithm converges to the optimal MVDR solution within finite steps no greater than the filter dimension. Theoretical analysis establishes formal convergence of the proposed conjugate AV algorithm. Our experiments using the synthetic and real speech data show favorites of the new proposal over the state-of-the-art approaches.