Klub nazwano na cześć nowojorskiego hotelu Waldorf-Astoriahttps://web.archive.org/web/20170312033627/http://www.astoria.bydgoszcz.pl/index.php/jak-kolejarze-zaoyli-astori dostęp 8-03-2017. Pierwszym prezesem został Bernard Mrowiński, pracownik Warsztatów Kolejowych. Początkowo uprawiano tylko piłkę nożnąJerzy Długosz: „Astoria” – klub mistrzów i rekordzistów [w:] Kalendarz Bydgoski 1999. Drużyna występowała w rozgrywkach B klasy. Treningi odbywano na otwartym terenie przyległym do Kanału Bydgoskiegohttp://www.astoria.bydgoszcz.pl/index.php/historia/historia-klubu dostęp 8-03-2017. W kolejnych latach zakładano inne sekcje sportowe: lekkoatletyczną (1925), pływacką (1927), koszykówki, tenisa stołowego, boksu, łyżwiarstwa szybkiego (1929) oraz szermierczą (1930). W okresie międzywojennym na najwyższym poziomie stała sekcja boksu, która w 1933 plasowała się na trzecim miejscu na Pomorzu, a w latach.1935-1936 była mistrzem okręgu. W 1937 bokser Bronisław Krzemiński w plebiscycie Tygodnika Sportowego na najlepszego sportowca Pomorza uzyskał 2. miejsce.