In this study, we examined the applicability of coda wave interferometry (CWI) technique, which was developed to characterize seismic waves, to detect and evaluate change in the velocity of ultrasonic waves in concrete due to acoustoelastic effect. Ultrasonic wave measurements and compressive loading tests were conducted on a concrete specimen. The measured wave signals were processed with CWI to detect and evaluate the relative velocity change with respect to the stress state of the specimen. A phase change due to the acoustoelastic effect of concrete was clearly detected in the late-arriving coda wave. This shows that the relative velocity change of ultrasonic waves in concrete due to the acoustoelastic effect can be evaluated successfully and precisely using CWI.