We have developed the theoretical foundation and technical details of a migration method using a local-cosine-bases (LCB) beamlet propagator. A beamlet propagator for heterogeneous media based on local perturbation theory is derived, and a fast implementation method is constructed. The use of local background velocities and local perturbations results in a two-scale decomposition of beamlet propagators: a background propagator for large-scale structures and a local phase-screen correction for small-scale local perturbations. Because of its locally adaptive nature, the beamlet propagator can handle strong lateral velocity variations with improved accuracy. For high-efficiency migration, we use a table-driven method and apply some techniques of sparse matrix operations. Compared with the Fourier finite-dif-ference and generalized screen propagator methods, the image quality and computational efficiency are similar. In some cases, we see fewer migration artifacts around and inside salt bodies with our method. We attribute this to the better high-angle accuracy of beamlet propagators in strong-contrast media. Numerical tests using synthetic data sets of the SEG-EAGE 2D salt model, Marmousi model, and Sigsbee 2A model demonstrate its high accuracy and reasonable efficiency. Another special feature of LCB beamlet migration is the availability of information in the local wavenumber domain during migration, which can be used to correct acquisition aperture effect and for other processing. Compared to beamlet migration using the Gabor-Daubechies frame (GDF) propagator, LCB migration is much more efficient because LCB is an orthonormal basis, whereas GDF has redundancy (usually greater than two) in the decomposition.