Workflow nets were introduced by Wil in the mid-90s as a subclass of Petri nets tailored towards modelling business processes. They are now the de-facto standard in process mining. We study the complexity of the reachability problem on workflow net classes with the varying properties of quasi-liveness, free-choice and the option to complete. This yields eight classes in total. A workflow net has the option to complete if the final marking is reachable from every state and it is quasi-live if every transition can be fired in some reachable marking. Our main result is a strong dichotomy: on safe workflow nets, the reachability problem is either in PTIME or PSPACE-complete (assuming PTIME and PSPACE are different). This dichotomy becomes all the more apparent when we drop safeness: then, the reachability problem is either in PTIME or becomes at least PSPACE-hard or even Ackermann-complete. More specifically, we show that the properties of being free-choice and having the option to complete are necessary and sufficient to obtain PTIME-complexity. Our proofs make strong use of several of Wil’s results on the structure theory of Petri nets, in particular of his work on lucency.