In this study, the adsorption of methylene blue (MB) from aqueous solutions on palm frond base (PFB) and palm leaflets (PL) was investigated. The adsorbents were characterized by elemental analysis using X-ray fluorescence (XRF), Fourier transform infrared (FTIR) spectroscopy, Brunauer, Emmet, and Teller (BET) technique, and scanning electron microscopy (SEM). The pH variation, contact time, and temperature effects on adsorption capacities were studied. Maximum removal adsorption was observed at pH 6. The contact time required to obtain the equilibrium was 50 and 100 min at 25 °C, for PFB and PL, respectively. Experimental adsorption data were modeled by Langmuir, Freundlich, and Temkin isotherms. The adsorption process is according to the Langmuir isotherm model for both adsorbents, with high correlation coefficients (R2 > 0.99) at different temperatures. The maximum adsorption capacities of MB on PFB and PL calculated from the Langmuir isotherm model were 70.87 and 72.3 mg/g at 55 °C, respectively. The modeling of the experimental data according to the pseudo-first- and pseudo-second-order kinetic models showed the result that the MB adsorption processes on PFB and PL followed a pseudo-second-order kinetics. Thermodynamically, adsorption of MB on PFB and PL was endothermic, spontaneous, and achievable at 25–55 °C. These results indicated that palm frond base and palm leaflets would be suitable adsorbents for methylene blue in wastewater.