Steve Ray has a list of 35 loaded Questions for "Bible Christians" (quotation marks his)(link to the whole list). This is number 29/35. I'm trying to provide the answers in a common format, for easy reference.
29) If the early Church believed in sola Scriptura, why do the creeds of the early Church always say “we believe in the Holy Catholic Church,” and not “we believe in Holy Scripture”?
Because the early Christians knew that the creeds themselves were summaries of Scriptural teaching. As Thomas Aquinas explained it: "It was necessary to collect in a single text the various truth transmitted in various places of the Sacred Scriptures so that the faith would be more readily at hand." (for more discussion)
Believing in "the Holy Catholic Church" does not mean what many Roman Catholics and Eastern Orthodox try to suggest that it means (a more complete explanation here). Very briefly it means believing that there is one, not putting one's faith in men.