Tussen 1909 en 1912 was er in Rotterdam ook een club die (RVV) Celeritas heette. Toen deze club zich met de naam Celeritas wilde inschrijven bij de KNVB was dat niet mogelijk, omdat er in Den Haag al een voetbalclub bestond en ingeschreven was met dezelfde naam. Het bestuur besloot deze club dan maar te noemen naar de scheepswerf waar de meeste spelers ook werkzaam waren; Wilton Feyenoord. De voetbalclub Feyenoord werd "geboren" en van die club is de geschiedenis meer dan bekend.
De naamgeving van de club komt van het Latijnse celeritas dat snelheid betekent. Celeritas was in 1907 het resultaat van het samengaan van de clubs HDS, Hercules en Victoria. Celeritas startte op een veld aan de Bosjes van Pex bij de huidige Daal en Bergselaan. Verhuizing naar de buurt van de huidige Thomsonlaan volgde enige tijd later maar ook dat duurde niet lang. In 1914 werd in de Westduinen gespeeld. Net als zoveel andere clubs verhuisde men in 1923 naar het pas voltooide Zuiderpark waar ook ADO, VCS, de Ooievaars en RVC speelden. Celeritas bleef 23 jaar in het Zuiderpark en verhuisde in 1949 naar een toenmalige uithoek van de stad op de kruising van de Leyweg en de Wateringse Noordweg. In 2009 voetbalde Celeritas daar nog en had er drie velden. Doordat de club in de Vinex-wijk Wateringse Veld lag was er een goede basis voor een gezonde sportvereniging.
Oorspronkelijk werd er alleen met seniorenelftallen gespeeld. Het eerste elftal haalde al in 1911 de hoogste klasse van de HVB (Haagsche Voetbal Bond) waar tegen de toen bekende clubs ADO, VCS en HBS werd gespeeld. Eind jaren 1910 wordt het eerste elftal kampioen van de HVB en promoveert naar de 3e klasse NVB (de voorloper van de KNVB). Pas vanaf 1926 kreeg Celeritas jeugdelftallen. Tijdens de Tweede Wereldoorlog startten er enkele pupillenelftallen.
Ook Dick Advocaat speelde in 1956/57 enkele maanden bij Celeritas. Hier kon men eerder lid van een voetbalclub worden dan elders, namelijk al met 9 jaar. Tot 1955 speelde Celeritas in sportief opzicht een marginale rol. Meestal was deze in de 4e klasse KNVB, district West-II. In de jaren 1950 groeide Celeritas enorm omdat de Haagse naoorlogse uitbreidingswijken Morgenstond, Moerwijk en Bouwlust enorme hoeveelheid jeugdspelers opleverde. In 1966 telde Celeritas 20 jeugdelftallen enige jaren later zelfs 27 eftallen tussen 10 en 18 jaar. Celeritas had na de ADO de grootste jeugdafdeling van Den Haag. Sportief ging het ook in die jaren uitstekend. Promotie naar de Tweede klasse volgde in 1959. Daarna ging het – met enkel korte oplevingen – langzaam bergafwaarts naar de onderste regionen van het amateurvoetbal namelijk naar de 4e klasse KNVB.
In het seizoen 1975/76 in de Derde Klasse A van de KNVB gaat het ineens veel beter en staat men halverwege de competitie ruim op kop; de tweede helft van de competitie verloopt moeizaam, maar ook de concurrenten (HVV en van Nispen) laten steken vallen en een 4-0 overwinning op Woerden betekent het kampioenschap van de Derde Klasse A van de KNVB en promotie naar de Tweede klasse van de KNVB.
Het 1e elftal, dat in het daarop volgende seizoen 1976/77 in de Tweede klasse van de KNVB als vierde eindigde achter VIOS, DHC en VELO, behaalde het beste resultaat in het gehele bestaan van de vereniging. In het seizoen daarop 1977/78 behaalde Celeritas de twaalfde plaats in de Tweede Klasse van de KNVB en degradeerde Celeritas weer naar de Derde klasse KNVB. In de daarop volgende seizoenen speelde Celeritas afwisselend in de 3e- en 4e klasse.
Ondanks enkele eerdere pogingen tot fusie met clubs als Triomph en BTC –de gemeente Den Haag moedigt fusies aan om clubs economisch en financieel sterk te houden– ging Celeritas in het seizoen 2014/15 een samenwerking aan met SVH. Deze samenwerking duurde twee seizoenen.