LTG Kellogg was born in 1944 at Wright-Patterson Army Air Corps Base (before it was Air Force) in Dayton, Ohio. His father was Army Air Corps, so he moved around a lot. After graduating high school in Long Beach, California, he went on to earn his undergraduate degree at Santa Clara University, where he also joined ROTC. He was commissioned into the United States Army in 1967. After the officer basic course at Ft. Benning, he completed airborne training and Ranger School. He was assigned to the 101st Airborne, and within days deployed to Vietnam. There he served first as a recon platoon leader before and during Tet, under the command of then-LTC David E. Grange, Jr. (the elder). During that time, he fought in two major engagements, one against the NVA Dong Nai Regiment in War Zone D, and then during Tet at Bien Hoa Air Base. He lost one third of his platoon, including all of his squad leaders. After his six-month rotation, he served for several months as aide-de-camp to MG Olinto Barsanti, commander of the 101st Airborne. After Barsanti left Vietnam, Kellogg ended his first tour as a pathfinder, moving people and materiel into Hue to dislodge the NVA and VC from the citadel. On his second tour, he served with as a Special Forces officer working with the New Zealand Special Air Services (SAS).