Although a detailed analysis of land use and land cover (LULC) change is essential in providing a greater understanding of increased human-environment interactions across the coastal region of Bangladesh, substantial challenges still exist for accurately classifying coastal LULC. This is due to the existence of high-level landscape heterogeneity and unavailability of good quality remotely sensed data. This study, the first of a kind, implemented a unique methodological approach to this challenge. Using freely available Landsat imagery, eXtreme Gradient Boosting (XGBoost)-based informative feature selection and Random Forest classification is used to elucidate spatio-temporal patterns of LULC across coastal areas over a 28-year period (1990–2017). We show that the XGBoost feature selection approach effectively addresses the issue of high landscape heterogeneity and spectral complexities in the image data, successfully augmenting the RF model performance (providing a mean user’s accuracy > 0.82). Multi-temporal LULC maps reveal that Bangladesh’s coastal areas experienced a net increase in agricultural land (5.44%), built-up (4.91%) and river (4.52%) areas over the past 28 years. While vegetation cover experienced a net decrease (8.26%), an increasing vegetation trend was observed in the years since 2000, primarily due to the Bangladesh government’s afforestation initiatives across the southern coastal belts. These findings provide a comprehensive picture of coastal LULC patterns, which will be useful for policy makers and resource managers to incorporate into coastal land use and environmental management practices. This work also provides useful methodological insights for future research to effectively address the spatial and spectral complexities of remotely sensed data used in classifying the LULC of a heterogeneous landscape.