A rich body of empirically grounded results and a solid theory base have often been viewed as signs of a mature discipline. Many disciplines have frequently debated what they should accept as legitimate kinds of theories, the proper roles of theory, and appropriate reference disciplines. Computing education research (CER) in particular has seen a growing number of calls for the development of domain-specific theories for CER, an adaptation of theories from other fields, and engagement with theory-based experimental and predictive research in CER. Many of those calls share the same concerns and aims, yet they use very different vocabulary and lack a consensus over an essential concept: theory. This article presents sticking points and trouble spots in CER's theory debates and presents a number of suggestions and ways forward. Firstly, by slightly shifting towards a model-based view of science, CER can avoid centuries of conceptual baggage related to the concept of theory. Secondly, insofar as fields like design, engineering, and social science are considered to be legitimate parts of CER, the role of theory in many CER studies needs to be judged by the criteria of the philosophy of engineering, technology, and social science, not the philosophy of (natural) science. Thirdly, instead of force-fitting elements of ill-suited research paradigms from other disciplines, the philosophy of CER should focus on building a consensus on CER's own paradigm and describing the field's relationship with theory in CER's own terms.