Newman’s objection is sometimes taken to be a fatal objection to structural realism (SR). However, ambiguity in the definition of “structure” allows for versions that do not succumb to Newman’s objection. In this paper, I consider some versions of SR that maintain an abstract notion of structure yet avoid Newman’s objection. In particular, I consider versions suggested by Melia and Saatsi. They reject a solution that restricts the domain of the second-order quantifiers, and argue in favor of buttressing the language with intensional operators such as “it is physically necessary that...”. I argue that their favored solution effectively requires the former suggestion that they reject. This argument suggests that a notion of natural properties may be indispensable to SR.