Służba wojskowa thumb|Pomnik Bülowa w Berlinie thumb|Pomnik Bülowa w Dennewitz 2 kwietnia 1768 roku, mając 13 lat, Bülow wstąpił do pruskiego Pułku Piechoty „von Lottum” Nr 13, gdzie otrzymał stopień podchorążego. W 1775 roku awansował na podporucznika, zaś 1 kwietnia 1778 roku miała miejsce jego promocja na stopień drugiego porucznika (Sekondeleutnant). Niedługo później wziął udział w wojnie o sukcesję bawarską, w której jako młody oficer sprawdził się podczas walk pod Leopoldovem.
W 1786 roku Bülow został mianowany porucznikiem, zaś cztery lata później awansował na sztabskapitana. W 1793 roku odbyła się jego promocja na stopień kapitana. Będąc jednym z wyróżniających się kawalerów w pruskiej stolicy cieszył się szacunkiem króla Fryderyka Wilhelma II, który z tego względu wyznaczył na jego towarzysza wojskowego księcia Ludwika Ferdynanda. Po stronie księcia, z którym połączyła go żarliwa przyjaźń, uczestniczył w kampanii przeciwko Francji z lat 1793–1794, walcząc m.in. w bitwie pod Kaiserslautern i podczas . Za swój wkład w atak na szaniec w Bülow został 17 lipca 1793 roku odznaczony orderem Pour le Mérite. Po kampanii, 3 kwietnia 1794 roku uzyskał stopień majora.