Identification of novel probiotic strain candidates based on sequence information of currently available probiotic strains and their key biomarkers requires comprehensive functional evaluation to establish their contributions to human health. Potential functional molecular biomarkers play a vital role in facilitating the discovery of new probiotic strains through sequence similarity analyses, remarkably within metagenomic datasets and unexplored microbial “dark matter”. It is critical to evaluate probiotic properties beyond taxonomical identifications by including the most important functional, metabolic, antibacterial and immunological features, as well as by using them as a marker for selection of probiotics. This review highlighted some key molecular biomarkers of probiotics, but also considered challenges like lack of standardization and in vitro and in vivo data, and discussed potential for further use. Probiotic screening by molecular markers in combination with bioinformatic search technology, which might represent future development direction toward the generation of next-generation probiotic strains.