Bacterial regulatory small RNAs (sRNAs) play important roles in gene regulation and are frequently connected to the expression of virulence factors in diverse bacteria. Only a few sRNAs have been described for Pasteurellaceae pathogens and no in-depth analysis of sRNAs has been described for Actinobacillus pleuropneumoniae, the causative agent of porcine pleuropneumonia, responsible for considerable losses in the swine industry. To search for sRNAs in A. pleuropneumoniae, we developed a strategy for the computational analysis of the bacterial genome by using four algorithms with different approaches, followed by experimental validation. The coding strand and expression of 17 out of 23 RNA candidates were confirmed by Northern blotting, RT-PCR, and RNA sequencing. Among them, two are likely riboswitches, three are housekeeping regulatory RNAs, two are the widely studied GcvB and 6S sRNAs, and 10 are putative novel trans-acting sRNAs, never before described for any bacteria. The latter group has several potential mRNA targets, many of which are involved with virulence, stress resistance, or metabolism, and connect the sRNAs in a complex gene regulatory network. The sRNAs identified are well conserved among the Pasteurellaceae that are evolutionarily closer to A. pleuropneumoniae and/or share the same host. Our results show that the combination of newly developed computational programs can be successfully utilized for the discovery of novel sRNAs and indicate an intricate system of gene regulation through sRNAs in A. pleuropneumoniae and in other Pasteurellaceae, thus providing clues for novel aspects of virulence that will be explored in further studies.