Adaptive dynamic surface control (ADSC) is effective for solving the complexity problem in adaptive backstepping control of integer-order nonlinear systems. This article focuses on the ADSC design for parametric uncertain fractional-order nonlinear systems (FONSs). In each backstepping step, the virtual controller is driven to pass through a fractional dynamic surface whose fractional-order derivative can be calculated easily. An ADSC law that ensure tracking error convergence is designed. The proposed ADSC requires a stringent condition called persistent excitation (PE) to achieve parameter convergence. To relax this limitation, a prediction error is defined by using online recorded data and instantaneous data, and a composite learning law is proposed to utilize both the prediction error and the tracking error. Then, a composite learning ADSC (CLADSC) method is developed to guarantee tracking error convergence and accurate parameter estimation under an interval excitation condition that is weaker than the PE one. Finally, an illustrative example is presented to show the performance of our methods.