The club is named after Johann Jacob Astor, who was born in Walldorf in 1763 and later emigrated to the United States where he became a successful businessman. His descendants, founders of the Waldorf-Astoria Hotel, generously supported the town of Walldorf and the new football club, formed in 1908, was named Astoria in his honour.
The club was formed on 15 February 1995 through the union of the 1. FC 08 Walldorf and the football department of SG Walldorf Astoria 02. The new club advanced to the Verbandsliga Nordbaden (V) in 2001. Winning the Verbandsliga in 2007, the club was promoted to the Oberliga Baden-Württemberg.
Like TSG 1899 Hoffenheim the club is supported by Dietmar Hopp, the founder of software maker SAP. Hopp initiated negotiations to merge FC Astoria Walldorf, TSG Hoffenheim, and SV Sandhausen to create FC Heidelberg 06 with the long-term objective of reaching the Bundesliga, Germany's first division league. The talks were abandoned in 2005 due to the resistance of the latter two clubs, and the failure to agree on whether the new side's stadium should be located in Heidelberg or Eppelheim.
A North Baden Cup win in 2013–14 earned the club the right to enter the first round of the 2014–15 DFB-Pokal, the German Cup, for the first time. In the same season the club also won the Oberliga title and earned promotion to the tier four Regionalliga Südwest for the first time.
FC Astoria Walldorf plays its home matches in the FC-Astoria stadium which features a natural turf field and two artificial turf fields. During the 2006 World Cup the facility was used as the training ground of the Costa Rican national side.