UJA Alfortville was formed in 1926 under the name Union de la Jeunesse Arménienne d'Alfortville. In 2008, following the club's promotion to the Championnat de France amateur for the 2008-09 season, Alfortville changed its name to its current one after it was recommended by the club's new partner Michel Moulin.
Over the course of a decade, Alfortville has quickly ascended up the French football league system. In 1998, the club was promoted from Promotion d'Honneur. In the following season, Alfortville earned promotion to the Division d'Honneur Régionale and proceeded to advance to the Division Supérieure Régionale two seasons later in 2000. The club remained in the seventh division for six years before achieving promotion to the Division d'Honneur of the Île-de-Franceregion. After one season, Alfortville ascended to the 5th level of the system, CFA 2. The club won its group in the first season, thus earning promotion to the Championnat de France amateur for the 2008–09 season. After two seasons in the CFA, Alfortville were administratively promoted to the Championnat National by the DNCG after the club appealed to the organization to contest an illegitimate win by the club that finished ahead of them in the standings.