We have explored the possibilities and challenges of structure-based virtual screening (SBVS) against the human histamine H4 receptor (H4R), a key player in inflammatory responses. Several SBVS strategies, employing different H4R ligand conformations, were validated and optimized with respect to their ability to discriminate small fragment-like H4R ligands from true inactive fragments, and compared to ligand-based virtual screening (LBVS) approaches. SBVS studies with a molecular interaction fingerprint (IFP) scoring method enabled the identification of H4R ligands that were not identified in LBVS runs, demonstrating the scaffold hopping potential of combining molecular docking and IFP scoring. Retrospective VS evaluations against H4R homology models based on the histamine H1 receptor (H1R) crystal structure did not give higher enrichments of H4R ligands than H4R models based on the beta-2 adrenergic receptor (β2R). Complementary prospective SBVS studies against β2R based and H1R based H4R homology models led to the discovery of different new fragment-like H4R ligand chemotypes. Of the 37 tested compounds, 9 fragments (representing 5 different scaffolds) had affinities between 0.14 and 6.3 µM at the H4R.