We have explored the possibilities and challenges of structure-based virtual screening (SBVS) against the human histamine H₄ receptor (H₄R), a key player in inflammatory responses. Several SBVS strategies, employing different H₄R ligand conformations, were validated and optimized with respect to their ability to discriminate small fragment-like H₄R 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 H₄R ligands that were not identified in LBVS runs, demonstrating the scaffold hopping potential of combining molecular docking and IFP scoring. Retrospective VS evaluations against H₄R homology models based on the histamine H₁ receptor (H₁R) crystal structure did not give higher enrichments of H₄R ligands than H₄R models based on the beta-2 adrenergic receptor (β₂R). Complementary prospective SBVS studies against β₂R-based and H₁R-based H₄R homology models led to the discovery of different new fragment-like H₄R ligand chemotypes. Of the 37 tested compounds, 9 fragments (representing 5 different scaffolds) had affinities between 0.14 and 6.3 μM at the H₄R.