In recent years, discovery proteomics has emerged as a pivotal tool in biological research, especially when studying the intricate relationships among multiple organisms. To delve deeper into these interactions, we pioneered a bottom-up proteomics workflow. Using nanoLC-MS/MS and a label-free quantification method, this work specifically examines the differential protein expression in fleas (Ctenocephalides felis felis) that have been experimentally infected with Bartonella henselae, the causative agent of cat scratch disease (CSD). Our detailed methodology, from protein cleanup to data analysis using the Proteome Discoverer software, is meticulously outlined to aid other researchers in adopting and adapting this workflow for their own multi-organism studies. This versatile protocol serves as a foundational guide for examining multiple proteomes from varied taxonomic lineages, exemplified in our cat-flea-bacterium investigation.