Since priests were not originally expected to be celibate, many must have been married when celibacy was first introduced. So what happened to the wives during this time when the institution started?
The women all died. That was about a thousand years ago, after all.
When the edict went out, the ruling was that married men would no longer be ordained, not that the priests who were married would get rid of their wives. Eventually, this meant that all of the women married to priests would either become widows or the priests would become widowers.
Below I was asked for a citation, so I'll go ahead and add this as an amendment. It was apparent that celibacy was highly preferred in the West by the time of the Quinisext Council, which mentions that the East does not have such a preference (a case of an exception proving that the rule exists). During the 11th century, Gregory VIII took dramatic and active efforts to eliminate all future married clergymen, and the Second Lateran Council forbid married clergymen completely. But by that time it had already been two generations since bishops were forbidden from ordaining married men anyway.