La nouvelle sur laquelle se base le film fait partie du dixième roman des aventures de Matt Scudder, écrit par Lawrence Block. Il existe 18 tomes consacrés au personnage, le dernier ayant été publié en 2011. Cette série de romans a par ailleurs déjà fait l'objet d'une adaptation cinématographique, Huit millions de façons de mourir (1986), de Hal Ashby avec Jeff Bridges, mais le tome adapté n'était pas le même que chez Scott Frank.
Le roman était, dans un premier temps, censé être adapté par Joe Carnahan, qui s'était déjà attelé à un sujet similaire dans Narc (2002), un flic sous couverture cherchant à prouver le meurtre d'un policier par des narco trafiquants. A ce moment, Harrison Ford était encore attaché au projet pour jouer le personnage principal. C'est finalement Liam Neeson qui interprète Matthew Scudder et Scott Frank qui réalise le film.
Le film fut entièrement tourné à New York City. Les scènes filmées à Brooklyn, au Green-Wood Cemetery, Sunset Park et Clinton Hill furent véritablement tournées sur place, tout comme les séquences ayant lieu dans le Queens (College Point et Malba) et sur Manhattan (New York Public Library et Washington Heights).
Lawrence Block, qui a été invité par les producteurs à assister au tournage sur le plateau, reconnaît avoir enfin découvert la version réelle de son personnage Matthew Scudder : "Les lecteurs me demandent souvent qui pourrait incarner mon Matt Scudder idéal, et j'ai tendance à changer de sujet de conversation. Mais je peux maintenant vous avouer que, depuis que je l'ai vu dans Michael Collins [1996, de Neil Jordan], Liam Neeson était au sommet de ma liste d'acteurs capables d'incarner le personnage. Je ne pourrais être plus heureux quant au choix de la star ou du réalisateur, tous deux étant de véritables artistes et de brillants professionnels. Mon livre est entre de bonnes mains."
Scénariste à la base (Hors d'atteinte, Minority Report), Scott Frank en est à sa deuxième réalisation de long-métrage avec A Walk Among The Tombstones.
Scott Frank s'est lancé dans l'adaptation du roman de Lawrence Block depuis déjà plusieurs années. Il termina une première version du script en 2002, alors que D.J. Caruso était censé le réaliser. Finalement, Frank prendra lui-même la place de réalisateur et commencera seulement le tournage en mars 2013 (alors que Liam Neeson avait signé depuis mai 2012). Le tournage se termina enfin le 8 octobre 2013. Au total, douze années se sont écoulées entre le coup d'envoi de la production et la sortie du film en salles.
Ruth Wilson était supposée jouer le rôle de Joe Durkin, la coéquipière de Matt Scudder (Liam Neeson). Après que l'actrice ait tourné toutes ses scènes, Scott Frank décida au dernier moment de la couper au montage, pensant qu'il serait plus intéressant de faire de Matt Scudder un "héros solitaire"... 20 minutes de film furent ainsi supprimées.
Brian "Astro" Bradley, le jeune comédien qui interprète TJ, l'ado sans-abri que Scutter prend sous son aile, s'est fait connaître du grand public en atteignant la finale d'une émission de télé-crochet pour apprentis chanteurs, puis s'est ensuite tourné vers le cinéma. Il est apparu dans un épisode de la série Person of Interest, et en 2014, on l'a aperçu dans Echo.
Le tournage de Balade entre les tombes s'est déroulé dans des conditions météorologiques pénibles, en plein hiver, par des températures glaciales. Les enregistrements ont par moment dû être interrompus à cause de la neige qui s'abattait sur les plateaux. La scène la plus difficile à tourner fut celle dans le cimetière de Green-Wood. Elle a nécessité huit jours de tournage et la nécropole n'étant pas éclairée, tourner dans un tel endroit, en pleine nuit qui plus est, a causé quelques frayeurs aux techniciens...