O Sestao River foi fundado em 1996, exatamente após o Sestao Sport Club ser dissolvido por problemas de nivel financeiro. Fez sua estreia no mesmo ano, disputando as divisões inferiores do país; em sua história, alternou entre a Segunda División B e a Tercera División (equivalente à quarta divisão nacional). Seu melhor resultado foi a promoção para a Terceira Divisão em 2003-04, mas seria rebaixado na temporada seguinte.