In this paper, we introduce a new primitive — referred to as conditional random selection. This new primitive allows the random selection of a data record from the subset of data records that meet a specified condition. We present a new privacy-preserving protocol that implements the new primitive and is secure in the semi-honest model. At its core, it uses newly developed protocols for oblivious shuffling, oblivious swapping, and privacy-preserving less than comparison on binary values with shared output. We show the relevance of conditional random selection in various application scenarios.