This Letter presents a search for the production of new heavy resonances decaying into a Higgs boson and a photon using proton-proton collision data at $\sqrt{s}=13$ TeV collected by the ATLAS detector at the LHC. The data correspond to an integrated luminosity of 139 fb$^{-1}$. The analysis is performed by reconstructing hadronically decaying Higgs boson $(H\to b\bar{b})$ candidates as single large-radius jets. A novel algorithm using information about the jet constituents in the center-of-mass frame of the jet is implemented to identify the two $b$-quarks in the single jet. No significant excess of events is observed above the expected background. Upper limits are set on the production cross-section times branching fraction for narrow spin-1 resonances decaying into a Higgs boson and a photon in the resonance mass range from 0.7 to 4 TeV, cross-sections times branching fraction are excluded between 11.6 fb and 0.11 fb at a 95% confidence level.