Internal solitary waves (ISWs) have considerable energy to drive the mixing of water masses in the Sulu Sea. The propagation speed is a critical parameter in demonstrating the dynamic characteristics of ISWs. We collected 1354 groups of ISWs’ speeds from tandem satellite remote sensing images with short temporal intervals and analyzed their spatial and multi-scale temporal variations in the Sulu Sea. The wave speeds increase exponentially with water depth with a power of 0.26. The fortnightly spring/neap tidal currents cause daily variations of wave speeds up to 30%. In addition to the well-recognized stratification that leads to monthly variations of wave speed, the seasonal circulations lead to a maximum decrease of wave speeds by 0.27 m/s. With respect to interannual variations, the wave speeds increase in La Niña years and decrease in El Niño years, caused by the climatic modulation of ocean stratification.