Two algorithms for calculating overlaps between CIS (or TDDFT) type excited state wave functions are presented, one based on an expansion of overlap determinants into level 2 minors (OL2M) and the other based on an expansion of the wave functions into natural transition orbitals (ONTO). Both algorithms are significantly faster than previously available algorithms, with the ONTO algorithm reducing the cost of a single overlap element calculation by a factor of the square of the number of occupied orbitals in the system. The algorithm exhibits orders of magnitude faster calculations for large systems and significantly increases the size of systems for which TDDFT based nonadiabatic dynamics simulations can be performed. The OL2M algorithm is substantially slower for a single overlap matrix element but becomes preferred when overlaps between large numbers of states are required. Additionally, we test the accuracy of approximate overlaps calculated using truncated wave functions and show that truncation can lead to large errors in the overlaps. Lastly, we provide examples of applications for wave function overlaps outside the context of nonadiabatic dynamics.