McCulloch had earned the nickname "Black Bob" from the men of the Second Missouri Cavalry (C.S.). He drove his men hard on the march from Jackson to Brownsville, Tennessee. Upon their arrival, he immediately called to the general population for a guide. With several officers calling, one W.J. Shaw presented himself to Matt Ward, who in turn brought Shaw to McCulloch. Shaw informed McCulloch that he'd been a prisoner at Fort Pillow just a few days prior. Satisfied that Shaw was telling the truth, he agreed to employ Shaw as a guide It was about then that Nathan Bedford Forrest himself arrived in Brownsville to lead the attack.
The attack began in the morning. In the afternoon, Forrest sought to convince the garrison inside the fort to surrender, but failed. Forrest marshalled his troops, and the rush to take the fort began in earnest. McCulloch and the Second Missouri were among the first to enter the fort. The Confederates piled on top of each other to act as a human ladder, and McCulloch oversaw the fall of the fort.
After the fort fell, it's commanding officer, Major William Bradford, surrendered. McCulloch took his parole. Bradford, the leader of a regiment made of "Tennessee Tories", was despised by the Confederate forces. Nonetheless, McCulloch and Nathan Bedford Forrest each pleged that he would be safe in Confederate custody. Forrest even agreed to allow Bradford to bury his brother, Theodorick Bradford, who'd been killed early in the fight.
However, as the night wore on, Forrest realized that the burial was taking too long. McCulloch went with Forrest and Captain Charles W. Anderson to investigate. They found Private Matt Ward passed out drunk near Theodorick Bradford's grave. Ward was able to explain part of what happened, and McCulloch figured out the rest: Bradford had been pretending to drink with Ward until Ward became completely drunk. As Ward was under McCulloch's command, McCulloch took full responsibility. Forrest realized just how clever Bradford was, and forgave Ward (and by extension, McCulloch). Forrest admitted that even he'd been blinded by his sympathy for Bradford's deceased brother. Forrest and MCulloch realized that Bradford would be headed for Memphis, and began a pursuit. For McCulloch, who'd taken Bradford's parole, catching and killing Bradford was a personal matter.
In the end, Bradford was caught and shot dead, although McCulloch was not present.