Based on the first-order shear deformation (FSD) model and nonlocal elasticity theory, the simultaneous effects of shear and small scale on the nonlinear vibration behavior of functionally graded carbon nanotube-reinforced composite (FG-CNTRC) beams are investigated for the first time. To this end, the governing equations of bending and stretching with von Kármán geometric nonlinearity are decoupled into one fourth-order partial differential equation in terms of transverse deflection. A closed-form solution of the nonlinear natural frequency, which can be used in conceptual design and optimization algorithms of FG- CNTRC beams with different boundary conditions, is developed using a hybrid method of Galerkin and perturbation technique. First, the decoupled equation is reduced to a nonlinear ordinary one with respect to time by implementing the Galerkin method. Next, multiple scales perturbation technique is used to replace this nonlinear ordinary differential equation with a series of linear equations which can be solved analytically. Finally, numerical results are presented to compare with the existing ones in the literature as well as to study the effects of CNTs distribution, boundary conditions and nonlocal parameter on the frequency ratio. It is seen that the influence of CNTs distribution becomes more significant when the nonlocal parameter increases. Also, the difference between results obtained from the classical and nonlocal elasticity theories increases as the amplitude of vibration increases. Therefore, it is concluded that the classical elasticity theory is inadequate to predict the nonlinear vibration behavior of FG-CNTRC beams with large deformation.