An automated item selection procedure in Mokken scale analysis partitions a set of items into one or more Mokken scales, if the data allow. Two algorithms are available that pursue the same goal of selecting Mokken scales of maximum length: Mokken’s original automated item selection procedure (AISP) and a genetic algorithm (GA). Minimum sample size requirements for the two algorithms to obtain stable, replicable results have not yet been established. In practical scale construction reported in the literature, we found that researchers used sample sizes ranging from 133 to 15,022 respondents. We investigated the effect of sample size on the assignment of items to the correct scales. Using a misclassification of 5% as a criterion, we found that the AISP and the GA algorithms minimally required 250 to 500 respondents when item quality was high and 1,250 to 1,750 respondents when item quality was low.