Before unions were ever legal or recognized, they worked because of the force of solidarity, collective action and bargaining. You just simply couldn't fire and replace everyone at once.
It created a bargaining entity that the owner was forced to deal with because the alternative was closure.
EDIT: Frankly, if a union is relying on its legal recognition and backing for survival, it's already a zombie, dead-man-walking structure that is just going to fall apart in the long run. Unions must maintain solidarity and collective action and a healthy internal democracy and vibrant participation, or they'll just become a bureaucratic husk. Like most of the North American labour movement.