State space analysis is a popular formal reasoning technique. However, it is subject to the crippling problem of state space explosion, where its application to real world models leads to unmanageably large state spaces. In this paper we present algorithms which attempt to alleviate the state space explosion problem by taking advantage of the common practice of incremental development, i.e. where the designer starts withan abstract model of the system and progressively refines it. The performance of the incremental algorithm is compared to that of the standard algorithm for some case studies, and situations under which the performance improvement can be expected are identified.