The board lacked the power to fire him. He controls most of the company. They had persuasive power, sure. But if he had wanted to dig in and refuse to leave, he could have.
That sounded right, but I was curious where that gets quantified. You can find the information in Uber's Articles of Incorporation. Not sure if this is the most recent copy, but here's a version from 2013...
http://orfe.princeton.edu/~alaink/SmartDrivingCars/PDFs/Uber...
The stuff about voting rights and board members starts on page 16.
So while Travis holds the majority of the voting power, he doesn't hold a ton of real-world cachet because of circumstance around the company. Uber is in a relatively fragile period in it's journey and no one at the top can afford to disagree right now so he has to mostly do what the big chunk of investors collectively tell him to do. The hope is that they can stay calm, run on autopilot without Travis for a bit and guide this cruise missile right through an IPO if everything goes according to plan. Since the investors effectively control the supply of additional capital, they are in a unique position of power here relative to Travis.
I think Uber's downfall is a bit exaggerated in the rest of these comments here. They'll go through some troubling times, but they just need to stay calm, and guide the ship. A lot of the pieces are already in place thanks to Travis, but Uber doesn't necessarily need him to oversee the next milestone the same way they needed him the past couple of years of insane growth.
Shareholder meetings operate on one-(voting)-share-one-vote, so a majority shareholder ultimately controls the composition of the board. But if one of "his" directors, who his shares elected, breaks ranks and votes to fire him, simply owning the shares doesn't allow him to immediately override that vote. Kalanick could have voted out the board members opposed to him at the next shareholder meeting, and voted in sympathetic ones, who then might rehire him as CEO. But that's a different question than whether he could win any board vote simply by virtue of owning a majority of voting shares. Shares don't directly have board votes, they just elect directors who have board votes, who usually vote with the interests of the shares that elected them, but might not always. Besides exercising their personal judgment, directors also have independent legal responsibilities that may in some cases make it prudent for them to vote to fire even the person who put them on the board.
Of course they do.
_delirium already said it, but it bears repeating since so many are confused.