Ensemble optimal interpolation (EnOI) is a variant of the ensemble Kalman filter (EnKF) that operates with a static ensemble to drastically reduce its computational cost. The idea is to use a pre-selected ensemble to parameterize the background covariance matrix, which avoids the costly integration of the ensemble members with the dynamical model during the forecast step of the filtering process. To better represent the pronounced time-varying circulation of the Red Sea, we propose a new adaptive EnOI approach in which the ensemble members are adaptively selected at every assimilation cycle from a large dictionary of ocean states describing the Red Sea variability. We implement and test different schemes to select the ensemble members (i) based on the similarity to the forecast state according to some criteria, or (ii) in term of best representation of the forecast in an ensemble subspace using an Orthogonal Matching Pursuit (OMP) algorithm. The relevance of the schemes is first demonstrated with the Lorenz 63 and Lorenz 96 models. Then results of numerical experiments assimilating real remote sensing data into a high resolution MIT general circulation model (MITgcm) of the Red Sea using the Data Assimilation Research Testbed (DART) system are presented and discussed.