Olds was born Robert Oldys Jr. in Honolulu, Hawaii, on July 14, 1922, into an army family and spent much of his boyhood in Hampton, Virginia, where he attended elementary and high school. His father was Captain (later Major General) Robert Oldys (later Olds) (1896–1943), an instructor pilot in France during World War I, former aide to Brigadier General Billy Mitchell from 1922 to 1925, and a leading advocate of strategic bombing in the Air Corps. His mother, Eloise Karine Wichman Nott (1896–1926), died when Robin was four and he was raised by his father. He had one younger brother, Stevan Meigs (1924–1988), two younger paternal half-brothers, Sterling Meigs "Dusty" (1935–1995) and Frederick (1936), born from his father's third marriage to Helen Sterling and an older maternal half-brother, Carter Nott (1919–1998), born from his mother's first marriage to Frederick Dickson Nott.