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 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→bb¯) 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-section times branching fractions are excluded between 11.6 fb and 0.11 fb at a 95% confidence level.