Fundado em 2002, o Vaslui disputou duas temporadas seguidas na Liga II, até conseguir sua ascensão para a Liga I. Desta forma, tornou-se o primeiro clube, na história do futebol romeno, a alcançar a Liga I, com menos de três anos de existência.
Na sua primeira temporada na Liga I, o Vaslui terminou na décima quarta posição, escapando por pouco do rebaixamento. Já no ano seguinte, o clube obteve uma significatica melhora, terminando na oitava posição
Então, em seu terceiro ano na Liga I, o Vaslui chegou na sétima posição, garantindo assim uma vaga na Copa Intertoto da UEFA de 2008.