We examine the status of the threat posed to stellar-mass black hole candidates by the possible existence of Q-stars (compact objects with an exotic equation of state that might have masses well above the normally accepted maximum for standard neutron stars). We point out that Q-stars could be extremely compact (with radii less than 1.5 times the corresponding Schwarzschild radius), making it difficult to determine observationally that a given object is a black hole rather than a Q-star unless there is direct evidence for the absence of a material surface. On the other hand, in order for a Q-star to have a mass as high as that inferred for the widely favored black hole candidate V404 Cygni, it would be necessary for the Q-matter equation of state to apply already at densities an order of magnitude below that of nuclear matter and this might well be considered implausible on physical grounds. We also describe how rotation affects the situation and discuss the prospects for determining observationally that black hole candidates are not Q-stars.