The first experimental demonstration of an adaptive quantum state estimation (AQSE) is reported. The strong consistency and asymptotic efficiency of AQSE have been mathematically proven [A. Fujiwara, J. Phys. A 39, 12489 (2006)]. In this Letter, the angle of linear polarization of single photons, the phase parameter between the right and the left circularly polarization, is estimated using AQSE, and the strong consistency and asymptotic efficiency are experimentally verified. AQSE will provide a general useful method in both quantum information processing and metrology.