Ribosomal intervening sequences (IVSs) were recently proposed as genetic markers for microbial source tracking (MST). This study comprehensively investigated host specificities of IVSs within the 16S rDNA of 73 genera of dominant fecal bacteria using the approaches of bioinformatics and next generation sequencing (NGS). Thirteen types of IVSs were identified in silico to be associated with particular host species; they were found within bacteria of the genera Anaerovibrio, Bacteroides, Faecalibacterium, Mitsuokella, Peptostreptococcus, Phascolarctobacterium, and Subdoligranulum. Based on the DNA sequences of the thirteen types of IVSs, polymerase chain reaction (PCR) assays were developed. PCR amplifications using fecal DNA samples of target and non-target host species demonstrated that eight out of the 13 IVSs were highly associated with human, chicken/turkey, beef cattle/pig, or horse/pig/human feces. Based on the IVS polymorphisms, NGS was applied to search for single-host-associated IVSs from those linked to multiple host species. Consequently, a new type of IVS specific to beef cattle was found and confirmed by PCR amplification using cattle and non-cattle fecal samples. The results suggest that some IVSs may be used as the genetic markers for MST and that NGS may be useful in identifying novel host-specific genetic markers.