Simulated Annealing has been an effective tool in many optimization problems in VLSI CAD but its time requirements are prohibitive. In this paper, we report a parallel algorithm for a well established, simulated annealing based algorithm for the state assignment problem for finite state machines. Our parallel annealing strategy uses parallel moves by multiple processes, each performing local moves within its assigned sub-space of the state encoding space. The novelty is in the dynamic repartitioning of the state space among processors, so that each processor gets to perform moves on the entire space over time. This is important to keep the quality of the parallel algorithm comparable to the serial algorithm. On the average our algorithm gives quality results within 0.05% of the serial algorithm on 64 processors. Our algorithm is portable across a wide range of MIMD machines and gives superlinear speedups on all of them. For a large circuit, the runtime has been reduced from 11 hours to 10 minutes on a 64 processor machine.