The concept of off-diagonal geometric phases for mixed quantal states in unitary evolution is developed. We show that these phases arise from three basic ideas: (1) fulfillment of quantum parallel transport of a complete basis, (2) a concept of mixed state orthogonality adapted to unitary evolution, and (3) a normalization condition. We provide a method for computing the off-diagonal mixed state phases to any order for unitarities that divide the parallel transported basis of Hilbert space into two parts: one part where each basis vector undergoes cyclic evolution and one part where all basis vectors are permuted among each other. We also demonstrate a purification based experimental procedure for the two lowest order mixed state phases and consider a physical scenario for a full characterization of the qubit mixed state geometric phases in terms of polarization-entangled photon pairs. An alternative second order off-diagonal mixed state geometric phase, which can be tested in single-particle experiments, is proposed.