Object-oriented constraint programming (OOCP) combines two orthogonal but complementary programming paradigms into one-object-oriented programming (OOP) and logic constraint programming (LCP). Most practitioners of OOCP would agree that the design of a constraint-based model is the most time consuming and difficult part of OOCP. There is currently no systematic approach or methodology to follow when designing a model suitable for OOCP. The paper outlines a simple methodology that extends traditional object-oriented analysis and design (OOAD) to cover constrained variables and constraints used in OOCP. The proposed OOCP Methodology is an initial investigation into providing a more rigid set of guidelines to follow when designing constraint-based models. The paper presents the OOCP methodology using a simplified nurse rostering system as a case study.