The idealists will say that both processes should be planned and implemented concurrently. Both are "control" processes and are closely linked as describe below:
Configuration Management provides information about the relationships of Configuration Items (CI) through the Configuration Management Database (CMDB) and therefore, provides Change Management with an understanding of the impact of changes to the CI.
Request for Change (RFC) and records of changes are supposed to be stored in the CMDB (depending on the scope of the CMDB). This enables tracking of progress of changes.
CMDB should only be updated if there is a corresponding approved RFC and completed Change.
Some may say that Configuration Management process should be implemented first. Some may even say it should be the first ITIL process to be implemented since this process underpins all other ITIL processes.
The fact is that many companies have implemented some form of Change Management process, without a formal Configuration Management process. In organizations that have implemented both processes, the maturity of their Change Management process is usually far more than the other.
How is this possible?
With a good CMDB, Change Management is able to conduct more effective impact assessment and to implement changes in a more controlled manner, resulting in a more stable environment.
However, good impact assessment can still be performed even without a CMDB. The knowledge of the CI relationships, state of the CI, history and other relevant information for impact assessment are in the heads of the persons responsible for the state of the CI (also known as CI Owners). The knowledge could also be documented somewhere by the CI Owners ("CMDB" in its raw form). A good impact assessment can still be done if the Change Manager is able to consult with or bring the right persons (i.e. CI Owners) to the Change Advisory Board meeting.
In any case, even with a functioning CMDB, the Change Manager should still consult and invite the CI Owners to help assess changes, especially complex changes as these CI Owners will be able to provide much more information, knowledge and wisdom than a mere CMDB.
The recording of RFC and change related information is an activity performed within the Change Management process. Storage of RFC and records of changes are possible without a formal Configuration Management process as long as records are properly kept and maintained using a document management tool or filing system.
In summary, it would be ideal to be able to plan and implement both processes concurrently. But if you are constrained by time, money or project resources, you may choose to postpone the Configuration Management process implementation and focus on getting Change Management process up and running first. Getting the benefits of an improved process earlier (Achieving Quick Wins) is an important consideration when you are on the IT Service Management (ITSM) journey. Also, with the Change Management process introduced, there is a better understanding of how to scope and plan the Configuration Management implementation to link both processes together later on.