You should schedule some downtime to accomplish this and start with your network infrastructure. This includes any routers, switches and so on, followed by infrastructure servers, application servers, workstations, printers and devices. The exact order that you select really depends on the current structure of your network. If it is a routable network, you can migrate small groups on a rolling basis which would minimize user impact. If it is more of a flat network then you will have to do it all at once.
If I may add; You could start with staticly assigned DHCP, and a few foot soilders with wireshark. As stated above, depends on the critcal services/size and scope of the existing network.
Oh, and end-game, ACL enforced static mappings.
Here is a document to get you started; “Best Practices for Next-Generation IP Address Management” By Tim Roomy, BT Diamond IP