The main objective of this paper is to examine how theories of truth and reference that are in a broad sense Fregean in character are threatened by antinomies; in particular by the Epimenides paradox and versions of the so-called Russell-Myhill antinomy, an intensional analogue of Russell’s more well-known paradox for extensions. Frege’s ontology of propositions and senses has recently received renewed interest in connection with minimalist theories that take propositions (thoughts) and senses (concepts) as the primary bearers of truth and reference. In this paper, I will present a rigorous version of Frege’s theory of sense and denotation and show that it leads to antinomies. I am also going to discuss ways of modifying Frege’s semantical and ontological framework in order to avoid the paradoxes. In this connection, I explore the possibility of giving up the Fregean assumption of a universal domain of absolutely all objects, containing in addition to extensional objects also abstract intensional ones like propositions and singular concepts. I outline a cumulative hierarchy of Fregean propositions and senses, in analogy with Gödel’s hierarchy of constructible sets. In this hierarchy, there is no domain of all objects. Instead, every domain of objects is extendible with new objects that, on pain of contradiction, cannot belong to the given domain. According to this approach, there is no domain containing absolutely all propositions or absolutely all senses.