Recently a new class of composite Higgs models have been developed which give rise to naturally light Higgs bosons without supersymmetry. Based on the chiral symmetries of "theory space" involving replicated gauge groups and appropriate gauge symmetry breaking patterns, these models allow the scale of the underlying strong dynamics giving rise to the composite particles to be as large as of order 10 TeV, without any fine tuning to prevent large corrections to Higgs boson mass(es) of order 100 GeV. In this paper we show that the, size of flavor violating interactions arising generically from underlying flavor dynamics constrains the scale of the Higgs boson compositeness to be greater than of order 75 TeV, implying that significant fine-tuning is required. Without fine-tuning, the low-energy structure of the composite Higgs model alone is not sufficient to eliminate potential problems with flavor-changing neutral currents or excessive CP violation; solving those problems requires additional information or assumptions about the symmetries of the underlying flavor or strong dynamics. We also consider the weaker, but more model-independent, bounds which arise from limits on weak isospin violation. ©2002 The American Physical Society.