The use of malolactic starter cultures to improve the fermentation process and enhance wine quality and safety is becoming a common winemaking practice, increasingly preferred to spontaneous fermentation. Given its great oenological properties, Oenococcus oeni is the species most present in commercial brands of wine lactic acid bacteria (LAB) starters. Stress resistance, technological performances and safety are the key selection criteria to take into account when designing effective malolactic starters. Nowadays, new LAB strains are selected by exploiting advanced technological applications rather than the traditional screening methods based on a trial and error approach. In particular, the progress made in the fields of genetics and molecular biology, as well as in the whole genome sequencing projects, offers new tools to better characterize candidate starter strains. This review aims at providing an updated picture of the technological approaches that should be used to select LAB strains suitable for winemaking. In the near future, the full integration of phenotypic and genetic data will make it possible to rationally develop malolactic cultures that are specific for different types of wine.