Most cities have historically not regulated transportation providers where the customer contracts with the provider ahead of time, or they are regulated in a different class and much more leniently than taxis. "Black car" aka livery and limousine services have existed long before Uber, and were not breaking the law in cities where they operated.
Most cities consider taxis to be vehicles that can be hailed by riders at the curb, where the trip is not pre-arranged and the customer has no prior business relationship with the transportation provider. Although Uber now has the ability to book actual taxis in some cities, this is not the category in which Uber historically operated.
Uber was able to grow quickly in part because it tapped into the large established base of private car services. These services existed in cities all over the world, but there was no unified interface to book cars with them. That's the niche that Uber filled. If you talk to many drivers today, they work for these companies (or own their own small company) and use Uber to fill their downtime.
For more information on this, see: "How does Uber overcome taxi medallion regulations?" on Quora: https://www.quora.com/How-does-Uber-overcome-taxi-medallion-...
> Before Uber and ride sharing, not all cars with personal driver for hires were taxis. You also had livery cars (such as limousine or black cabs) and various other systems. In cities that enforce a medallion system, taxis have more rights than livery cars; specifically, they are authorized to respond to street hails, ie to pick a passenger that waves at them from the street. Livery cars only can take a pre-arranged trip. As the number of medallions is limited, the right to take street hails is exclusive to taxis.
> Uber can be used to book taxis in certain markets but the vast majority of Uber trips are not taxi rides. Originally, the Uber service was what is Uber Black today, bringing business to livery cars. The cars were already licensed, insured and authorized to operate. They weren’t allowed to pick up a person on the street (still aren’t) but if a trip was booked to the app, it’s considered pre-arranged. So this didn’t change much from a legal perspective.