Norman enlisted in the Texas Army National Guard in 1962 and served until 1968 while playing for the Dallas Cowboys. He married his junior high sweetheart, Margaret Ann Clinkscales, on December 22, 1962 and had three daughters before becoming widowed in 1991. The Reverend Jesse Jackson eulogized Norman's late wife. In 1995, Norman married Ivette Hightower, daughter of the late Master Chief Harry Hightower for whom Hightower Hall at Naval Station Norfolk was named. The Reverend Jesse Jackson officiated the wedding.