Antibodies are important biomolecules that are often designed to recognize target antigens. However, they are expensive to produce and their relatively large size prevents their transport across lipid membranes. An alternative to antibodies is aptamers, short (∼15-60 bp) oligonucleotides (and amino acid sequences) with specific secondary and tertiary structures that govern their affinity to specific target molecules. Aptamers are typically generated via solid phase oligonucleotide synthesis before selection and amplification through Systematic Evolution of Ligands by EXponential enrichment (SELEX), a process based on competitive binding that enriches the population of certain strands while removing unwanted sequences, yielding aptamers with high specificity and affinity to a target molecule. Mathematical analyses of SELEX have been formulated in the mass action limit, which assumes large system sizes and/or high aptamer and target molecule concentrations. In this paper, we develop a fully discrete stochastic model of SELEX. While converging to a mass-action model in the large system-size limit, our stochastic model allows us to study statistical quantities when the system size is small, such as the probability of losing the best-binding aptamer during each round of selection. Specifically, we find that optimal SELEX protocols in the stochastic model differ from those predicted by a deterministic model.