The Boltzmann equation without the angular cutoff is considered when the initial data is a small perturbation of a global Maxwellian and decays algebraically in the velocity variable. We obtain a well-posedness theory in the perturbative framework for both mild and strong angular singularities. The three main ingredients in the proof are the moment propagation, the spectral gap of the linearized operator, and the regularizing effect of the linearized operator when the initial data is in a Sobolev space with a negative index. A carefully designed pseudo-differential operator plays a central role in capturing the regularizing effect. In addition, some intrinsic symmetry with respect to the collision operator and an intrinsic functional in the coercivity estimate are essentially used in the commutator estimates for the collision operator with velocity weights.