One of the key figures in preserving the remnants of the North American bison herds at the end of the 19th Century, "Buffalo" Jones, set up the first known buffalo ranch in Oklahoma (he's the one who rode a buffalo in "Buffalo Bill's Wild West Show" and was the first to crossbreed them with domestic cattle but you get a non-reproducing 'mule'.) He did manage to ride a few of his in several years of working with them daily, pull a wagon short distances (more of a training project/stunt), and did herd them on horseback around his ranch. So domestication to a surprising extent and in a very short period is OTL-proven more than any of us would expect although no one has had Jones's success since.
Several hundred thousand buffalo are commercially ranched in the U.S. now but the buffalo ranchers tell me even a big horse isn't much to herd buffalo with while just fine for cattle.
Estimates are 30-100 million bison roaming North America still by mid 19th century and they're ideally adapted to the Great Plains and virtually no inputs, which seems more like a breeding program like many Native agriculture practices (plant and forget then harvest instead of endlessly weed and feed). Bison are so low input, low maintenance that our assumptions about what domestic animals require make them hard to imagine and presumed entirely wild, just as Indians harvesting 40-60% of their daily calorie intake from plants in the river valleys that they'd seeded but didn't till or put in neat fields like Europeans would be no-till farming instead of lucky foraging (and the women did all the farming work so it didn't interest male observers much as important compared to hunting stories.) Cattle are much more vulnerable to predators than bison who can stop a grizzly bear attack head-on or a wolf pack so there's just not much for a herdsman to do. Herding buffalo to a valley or spot, to then drive them over a cliff to let the fall kill them by the dozens, goes back thousands of years including erecting corrals/fencing to do it so workarounds for the lack of a cowhorse are legion already.
At 600lbs. to 2,000 lbs. per animal they dress out at about 60% usable meat as proportion of total body weight and it's 50% higher in protein than beef, so the bison-eaters were as much as a foot taller, more muscular, and longer-lived than the white invaders or coastal Indians with primarily fish diets, from both early visitors accounts and their own remarks about losing substantial lifespan and height switching to the European diet in the 1860's-1890's. If you're fighting with muscle-powered weapons where reach matters, that's a big advantage.
As for protein I'm surprised at the oversight in the discussion of the tens of millions of deer, millions of elk (early explorers describe watching thousands of elk in a single herd pass them by frequently, only the bison more numerous and impressive as an individual herd could be 3 million bison and take several days to walk past.) Salmon (caught with nets, fishing weirs, elaborate systems in rivers/coasts/lakes, and smoked for months of eating), millions of tasty passenger pigeons, vast quantities of rabbits and other small mammals...varied protein sources weren't an issue and were probably superior in range and access to anywhere in European or Asian civilizations of the time (or now.) For that matter beans, in many varieties and grown far into North America are a crop staple just like sunflower seeds, acorns ground into flour, pinon nuts, walnuts, grasshoppers, ants, beetles, snakes, alligators, clams, oysters, lobsters, crab, shrimp, crawfish, pike, trout, sturgeon, bass, catfish, bears, beavers, etc. were all common protein sources depending on region and season.
Deer and elk are ranched too so certainly could have been then...putting out crop-based feed such as dried corn that the animal can't find in the wild seems to be a key (just like domestic dogs chose our butchering scraps by a nice fire over searching for carrion in the wilderness all day.)
While bison are ridable, like a beef bull or oxen is, they're too wide for comfort and too moody. Like oxen, training them to pull wagons, wood sledges carrying stones/bricks/ores/ice/wood, chariots, powered machinery seems very doable given enough time and breeding. So while bison cavalry would be nearly unstoppable short of a .50-70-500 chambered Gatling Gun (1866-1873), bison war chariots or bison-drawn artillery/siege engines would be much more doable with enough time and breeding. With wagons or sledges or sleighs (bison move through heavy snow very well) you'd change transportation to far heavier cargos and greater ranges (in endurance, hydration, calorie-burn while grazing, foraging ability etc. a bison is quite a bit closer to a camel than a modern cow.
The big bison populations are out on the Great Plains, along the river valleys as these are big animals that prefer quite a bit of water every day and their herd size and movement requires rivers. The tribes stick to the river valleys for the same reason as does much of the game, trees, and edible plantlife so irrigation isn't as required at this stage as thought. There were elaborate irrigation canals in place long ago that caused the City of Phoenix, Arizona to locate there, others in N. America long mistaken for rivers/natural channels (despite being straight), and especially vast systems with the Mayans, the pre-Aztec tribes like the Mexica, and the pre-Incan tribes.
The brucellosis in the modern bison population goes by many names and was apparently contracted from modern cattle herds. The elk have it too. Horses, sheep, pigs, dogs, and people can get it (does species jump and kills several Americans every year as Undulant Fever.)