This study presents the first algal thallus (skeleton) archive of Asian monsoon strength and Red Sea influence in the Gulf of Aden. Mg/Ca, Li/Ca, and Ba/Ca were measured in Lithophyllum yemenense from Balhaf (Gulf of Aden) using laser ablation inductively coupled plasma mass spectrometry, and Mg/Ca ratio oscillation was used to reconstruct the chronology (34 y). Oscillations of element rates corresponding to the algal growth between 1974 and 2008 were compared with recorded climate and oceanographic variability. During this period, sea surface temperatures (SST) in Balhaf recorded a warming trend of 0.55°C, corresponding to an increase in Mg and Li content in the algal thallus of 2.1 mol-% and 1.87 μmol-%, respectively. Lithophyllum yemenense recorded decadal SST variability by Li/Ca, and the influence of the Pacific El-Niño Southern Oscillation on the NW Indian Ocean climate system by Ba/Ca. Additionally, algal Mg/Ca, Li/Ca, and Ba/Ca showed strong and significant correlations with All Indian Rainfall in the decadal range indicating that these proxies can be useful for tracking variability in the Indian monsoon system, possibly due to changes of the surface wind system, with deep water upwelling in summer, and a distinct seasonality.