Sutherland was estranged from his wife Anne for many years before her death in November 1888. Less than four months after her death, Sutherland married, on 4 March 1889, Mary Caroline (née Michell) Blair, with the Bishop of Florida, Edwin Garner Weed, officiating. causing a scandal as the conventional minimum period between the death of a spouse and remarriage being one year. Mary was the daughter of Rev. Richard Michell, DD, and the widow of Captain Arthur Kindersley Blair, formerly of the 71st Highland Light Infantry. Blair had resigned his commission in the Highlanders in 1861 and worked as a land agent and business manager for Sutherland; Mrs. Blair became Sutherland's mistress, and although Blair's death in 1883 was officially recorded as accidental, there was considerable speculation, at the time and later, that it may have been suicide or even murder.