A search is performed for the production of high-mass resonances decaying into a photon and a jet in 3.2 fb−1 of proton-proton collisions at a centre-of-mass energy of s√=13 TeV collected by the ATLAS detector at the Large Hadron Collider. Selected events have an isolated photon and a jet, each with transverse momentum above 150 GeV. No significant deviation of the γ+jet invariant mass distribution from the background-only hypothesis is found. Limits are set at 95% confidence level on the cross sections of generic Gaussian-shaped signals and of a few benchmark phenomena beyond the Standard Model: excited quarks with vector-like couplings to the Standard Model particles, and non-thermal quantum black holes in two models of extra spatial dimensions. The minimum excluded visible cross sections for Gaussian-shaped resonances with width-to-mass ratios of 2% decrease from about 6 fb for a mass of 1.5 TeV to about 0.8 fb for a mass of 5 TeV. The minimum excluded visible cross sections for Gaussian-shaped resonances with width-to-mass ratios of 15% decrease from about 50 fb for a mass of 1.5 TeV to about 1.0 fb for a mass of 5 TeV. Excited quarks are excluded below masses of 4.4 TeV, and non-thermal quantum black holes are excluded below masses of 3.8 (6.2) TeV for Randall-Sundrum (Arkani-Hamed-Dimopoulous-Dvali) models with one (six) extra dimensions.