The Gram-negative bacterium Acinetobacter baumannii causes life-threatening nosocomial infections, and has a near unparalleled capacity to develop multidrug-resistance. Small non-coding RNAs (sRNAs) regulate bacterial physiology, antibiotic resistance, and virulence in many pathogens; however, there has been limited characterisation of these important regulatory molecules in A. baumannii. Bioinformatic analysis of multiple whole-transcriptome RNA-seq datasets identified more than 40 putative sRNAs that were highly conserved in strains AB5075, AB307-0294, ATCC 17978, and ATCC 19606; four of these sRNAs were selected for initial functional characterisation. Fluorescent primer extension analyses defined the transcriptional start sites of sRNA_2, sRNA_4, sRNA_61, and sRNA_74 in strain AB307-0294, strongly suggesting they were true sRNAs. Deletion mutants in each of the four sRNA genes were constructed and analysed via label-free quantitative proteomics to identify protein production changes compared to the wild-type AB307-0294 strain. Notably, all four sRNA mutants showed increased production of proteins in the same fimbrial biogenesis system, which is predicted to be involved in A. baumannii attachment and/or biofilm formation. In addition, the sRNA_2 mutant showed decreased production of proteins involved in D-amino acid metabolism, the sRNA_4 mutant showed decreased production of proteins involved in type IV pili assembly and function, and the sRNA_61 mutant showed increased production of a fibronectin-binding protein, which is predicted to be a key bacterial adhesin. Each of the sRNA mutants showed no significant change in growth or swarming motility, but the sRNA_4 mutant showed a statistically significant, although slight, reduction in biofilm formation. In conclusion, this study has shown that A. baumannii sRNAs may regulate key virulence-associated proteins, and thus sRNAs may be novel candidates for therapeutic targeting in strains of multidrug-resistant A. baumannii.