In August 1914, Veltjens joined the army and rapidly rose to the rank of Vizefeldwebel. Toward the end of 1915, he transferred to the German Air Force and was assigned to Flieger Abteilung 23 in May 1916. His skills as a reconnaisance pilot were quickly recognized and by March 1917, he was flying single-seat fighters with Jasta 14. By the time he was reassigned to Jasta 18 in August, he'd already shot down five enemy aircraft. Veltjens assumed command of Jasta 15 for the first time on 18 May 1918. Two days later, he received the Knight's Cross with Swords of the Order of the House of Hohenzollern followed by the coveted Orden Pour le Mérite in August. On 22 August 1918, he assumed command of Jasta 15 for the second time, serving as its commanding officer until the end of the war. Veltjens' aircraft were often easily identified by a barbed arrow painted on the fuselage.
During World War II, Colonel Veltjens was Hermann Göring's personal emissary to Finland in 1940. In 1943, he was killed on a flight to Rome in an aircraft provided by Feldmarschall Kesselring. On Göring's behalf, he was to negotiate with Benito Mussolini for the removal of Italy's gold reserves to avoid capture by the approaching Allied forces.When the plane landed in Milano, the pilot was informed that British fighter aircraft where out to intercept his flight. As the pilot attempted to cross the Appenine mountains, he flew as low as possible to evade the British but the aircraft crashed into the side of a mountain near Piacenza. With the exception of one crew member, everyone aboard was killed.