A directional multilevel algorithm for translation-invariant oscillatory kernels of the type K(x, y) = G(x ?#xA0;y)e?k?em>x?em>y?/sup>, with G(x ?#xA0;y) being any smooth kernel, will be presented. We will first present a general approach to build fast multipole methods (FMMs) based on Chebyshev interpolation and the adaptive cross approximation (ACA) for smooth kernels. The Chebyshev interpolation is used to transfer information up and down the levels of the FMM. The scheme is further accelerated by compressing the information stored at Chebyshev interpolation points using ACA and QR decompositions. This leads to a nearly optimal computational cost with a small pre-processing time due to the low computational cost of ACA. This approach is in particular faster than performing singular value decompositions. This does not address the difficulties associated with the oscillatory nature of K. For that purpose, we consider the following modification of the kernel Ku = K(x, y)e?em>?ku¡¤(x?em>y), where u is a unit vector (see Brandt ). We proved that the kernel Ku can be interpolated efficiently when x ?#xA0;y lies in a cone of direction u. This result is used to construct an FMM for the kernel K. Theoretical error bounds will be presented to control the error in the computation as well as the computational cost of the method. The paper ends with the presentation of 2D and 3D numerical convergence studies, and computational cost benchmarks.