Brackenbury was born in the parish of Gainford. The nearby lordship of Barnard Castle was held by Richard, duke of Gloucester and Brackenbury had probably entered the duke's service by 1477. By 1479 he was treasurer of Gloucester's household . Two years later, he acquired the manor of Selaby , co. Durham.
Brackenbury's prospects were transformed by Gloucester's accession as Richard III in 1483. He was not at Richard's coronation, but less than a fortnight later, on 17 July, he was made constable of the Tower of London for life and master of the mint and keeper of the king's exchange in the Tower-one of relatively few northerners to receive major office in the south so early in the reign.
Brackenbury was thus constable of the Tower when Richard is believed to have ordered the death of his nephews, Edward V and Richard, duke of York, although no chronicler associates him directly with their deaths. Early writers give no details, and the version current after the execution of Sir James Tyrell in 1502 was that Brackenbury had hesitated to carry out their murder, and Richard accordingly commanded Tyrell to kill them. The most that can be said is that the scale of Brackenbury's subsequent reward makes it unlikely that his role in the affair had offended the king.