Już na jesieni 1939 r., po klęsce wrześniowej zaczęły samorzutnie powstawać zalążki przy-szłych oddziałów bojowych Batalionu, organizowane przez żołnierzy Wojska Polskiego, którzy uniknęli niewoli, oraz przez organizacje harcerskie. W ten sposób powstały pierwsze zręby  1 kompanii „Wigry”,  2 kompanii  „Szare Szeregi”, 3 kompanii „Szare Szeregi – Junior”, 4 kompanii „Watra”, 5 kompanii „Wysocki” (późniejszy kryptonim „Wysocki – Philips”), 6 kompanii „Wawerska” i 7 kompanii motorowej „Iskra”. Grupy te po nawiązaniu kontaktów z dowódcą IV Rejonu P.O.Z. (Polska Organizacja Zbrojna) majorem Stanisławem Steczkowskim „Zagończykiem” weszły w skład utworzonego Batalionu „Vistula”, jako kompanie o podanych wyżej numerach i kryptonimach. Po przekazaniu batalionu przez P.O.Z. w grudniu 1942 r. do Armii Krajowej, w marcu 1943 r. Batalion został przemianowany na Batalion imienia pułkownika Jan Kilińskiego i pod tym kryptonimem istniał do końca.