On the basis of computational design, a focused one-bead one-compound library has been prepared on microparticle-encoded PEGA₁₉₀₀ beads consisting of small tripeptides with a triazole-capped N-terminal. The library was screened towards a double point-mutated version of the human FKBP12 protein, known as the destabilizing domain (DD). Inspired by the decoded library hits, unnatural peptide structures were screened in a novel on-bead assay, which was useful for a rapid structure evaluation prior to off-bead resynthesis. Subsequently, a series of 19 compounds were prepared and tested using a competitive fluorescence polarization assay, which led to the discovery of peptide ligands with low micromolar binding affinity towards the DD. The methodology represents a rapid approach for identification of a novel structure scaffold, where the screening and initial structure refinement was accomplished using small quantities of library building blocks.