Faits : A. A._ a été blessé au cours d'une altercation à la sortie d'un établissement public à Neuchâtel le 28 août 2002. La personne à l'origine de ses blessures a été condamnée par le Tribunal de police du district de Neuchâtel le 12 février 2004. Le 1er mars 2004, A._ a saisi le département neuchâtelois compétent d'une demande fondée sur la loi fédérale sur l'aide aux victimes d'infractions (LAVI; RS 312.5) pour 30'000 fr. d'indemnité de tort moral (réduits depuis à 25'000 fr.) ainsi qu'une participation à ses frais d'avocat. B. Par décision du 14 novembre 2014, le Département de l'économie et de l'action sociale (DEAS) a rejeté la demande LAVI. La Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel a confirmé cette décision par arrêt du 6 avril 2016. C. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler l'arrêt cantonal et de renvoyer la cause à l'instance cantonale pour nouvelle décision lui accordant une indemnité pour réparation du tort moral. La cour cantonale se réfère aux motifs de son arrêt et conclut au rejet du recours. Consulté, l'Office fédéral de la justice renonce à prendre position.