Yes, you have to trust the company storing the passwords.
A good company can store passwords in ways that are secure to most hacking attempts. It isn't impossible to break the encryption typically used, but it is difficult enough that most thieves will not have the resources or time to make use of the data. They want the low effort password databases, not the difficult and expensive ones.