In a series of recent works, Kit Fine (The Journal of Philosophy, 100(12), 605–631, 2003, 2007) has sketched a novel solution to Frege’s puzzle. Radically departing from previous solutions, Fine argues that Frege’s puzzle forces us to reject compositionality. In this paper we first provide an explicit formalization of the relational semantics for first-order logic suggested, but only briefly sketched, by Fine. We then show why the relational semantics alone is technically inadequate, forcing Fine to enrich the syntax with a coordination schema. Given this enrichment, we argue, that that the semantics is compositional. We then examine the deep consequences of this result for Fine’s proposed solution to Frege’s puzzle. We argue that Fine has mis-diagnosed his own solution–his attempted solution does not deny compositionality. The correct characterization of Fine’s solution fits him more comfortably among familiar solutions to the puzzle.