Henry Cary Jr. was born in Colonial Virginia around the mid to late 1600s, the son of Henry Cary Sr., also a businessman and building contractor, and his wife, Judith Lockey. There are few surviving records of his early life but it is likely that he learned about contracting through his father. Cary married three times and had seven children, three with his first wife Sarah Sclater and four with his second wife, Ann Edwards.