A FESX foi fundada em 28/09/1976, em Assembléia Geral realizada às 20:00 no Clube de Regatas Saldanha da Gama, constituindo-se como sendo uma entidade de caráter desportivo amadorista para funcionar por tempo indeterminado, tendo como princípios básicos a organização permanente e representativa do jogo de xadrez, bem como o aperfeiçoamento, intensificação e progresso desse desporto. A fundação restou concretizada pela participação das seguintes associações e instituições:
A Diretoria da FESX empossada naquela oportunidade teve a seguinte composição:
A sede inicial encontrava-se localizada à Praça Costa Pereira, nº 52, Edifício Palácio do Café, salas 604 e 605, Centro, Vitória-ES.
A FESX permaneceu inativa desde a sua fundação, vindo a ser reativada por força da Assembléia Geral realizada em 23/09/1986, ocasião em que foi eleita a nova Diretoria, composta:
Neste ano a Federação realizou o campeonato estadual esporádico, tendo como campeão o forte enxadrista Namyr Carlos de Souza Filho, voltando a ficar inativa.
Contudo, em 1995, a FESX retomou as suas atividades, realizando os torneios anualmente, tendo como marco de sua estabilização definitiva a administração do Presidente Rogério Zanon da Silveira (1997/1998 e 1999/2000), quando passou a ter na Prefeitura de Vitória, através da Lei Jayme Navarro de Carvalho, a sua maior parceira nas realizações. Na administração de Zanon, a FESX realizou vários torneios FIDE fechados, para que os jogadores mais fortes viessem a obter rating, além da realização de vários torneios de altíssimo nível técnico, como o Magistral FIDE e a Copa dos Campeõees Estaduais.
Em 2001 a FESX realizou, pela primeira vez, a Semifinal do Campeonato Brasileiro, no Hotel Ilha do Boi.
Em 2002, realizou um Aberto do Brasil e outra Semifinal, além de conseguir a titulação de seu primeiro Árbitro Nacional de Xadrez junto à CBX.
Em 2003, novamente a FESX realizou a Semifinal do Brasileiro, praticamente assegurando esse torneio para todos os anos no calendário da Confederação Brasileira.
Desde o ano de 2000, todas as Finais do Estadual valem Rating FIDE e, desde 2001, as Semifinais também. Até Julho de 2004, a FESX contava com mais de 200 jogadores com rating estadual e mais de 20 com FIDE, tendo em 2003 classificado 2 jogadores para a Final do Brasileiro.