De lonely hearts-rubriek in een krant of tijdschrift is een plek waar de wanhopigste mensen op zoek gaan naar liefde en gezelschap. Het is zon rubriek waarvan je hoopt dat je die nooit zal hoeven te gebruiken om een partner te vinden of iemand anders op jezelf te attenderen. Dat laatste is al helemaal niet wenselijk als je eind jaren veertig als oorlogsweduwe in Michigan of New York woonachtig bent en enige rijkdom tot je beschikking hebt. Want dan bestaat de kans dat een charmante jongeman met de naam Raymond Fernandez op een dag contact met je opneemt.
Wat op het eerste gezicht een geschenk uit de hemel lijkt, heeft meer op met verdoemenis en hel. Ray Fernandez charmeert zijn slachtoffers zo dat ze verliefd op hem worden en hun geld aan hem beschikbaar stellen. Dan neemt hij wat hij nemen kan en verdwijnt, zijn slachtoffer achterlatend met een lege rekening en een gebroken hart. Hij kijkt daarna even de contactadvertenties na en gaat op weg naar de volgende weduwe. Dit gaat echter mis als de zoveelste weduwe hem doorheeft en achterna komt.
Deze psychotische Martha Beck laat haar liefde niet zomaar gaan en haalt hem over om samen verder te werken. Alleen is er één wijziging in het werkplan: na afloop vermoordt zij uit jaloezie de weduwen. En zo komt het geschifte koppel bekend te staan als de Lonely Hearts killers. Alsof de toegewijde rechercheur Elmer C. Robinson nog niet genoeg problemen heeft. Omdat zijn vrouw zich zonder schijnbare reden enkele jaren geleden door het hoofd schoot (netjes in de badkuip, want ze bleef natuurlijk wel een goede huisvrouw), moet hij alleen voor zijn jonge zoon zorgen. Hij raakt geobsedeerd door de zaak van de moordenaars en begint voor het eerst sinds de dood van zijn vrouw weer veldwerk te doen.
De openingsscène, waarin in een vrolijke sfeer prachtig naar de onverwachte zelfmoord van Robinsons vrouw wordt toegewerkt, is meteen de beste scène van de film. Daarna volgt de eerste van een aantal voice-overmonologen van James Gandolfini die de partner van Robinson speelt. Gandolfini heeft er een goede stem voor, maar de teksten zijn overbodig. Hoewel het de eerste keer nog wel handig is om even een snelle update te krijgen over Robinsons leven voor zijn entree in de film, wordt daarna voortdurend het voor de hand liggende of al op het scherm zichtbare vastgesteld.
Het is aardig om Travolta weer eens een redelijke rol te zien spelen, maar hij slaagt er niet helemaal in om met lichaamstaal het innerlijke conflict en de gevoelens van zijn zwijgzame personage over te brengen. Doordat regisseur Todd Robinson (jawel, de kleinzoon van de echte Elmer C. Robinson) daar wel op vertrouwt en de film dáár vooral omheen bouwt, blijft Lonely Hearts een wat oppervlakkige genrefilm met pretenties die niet waargemaakt worden. Mogelijk hebben budgettaire problemen een rol gespeeld, waardoor cruciale scènes niet gefilmd konden worden en Robinson van het beschikbare materiaal in de montagekamer een nieuw verhaal moest maken.
De uiteindelijke ontdekking van Robinson (de rechercheur) dat liefde en familie belangrijker zijn dan politiewerk heeft daardoor niet de diepgang die het eigenlijk zou moeten hebben om dit gegeven overtuigend over te laten komen. De enige ontdekking voor de kijker is dat Salma Hayek weer eens een echt goede rol speelt als de ernstig labiele psychopate die zelfs haar vriendje regelmatig de stuipen op het lijf jaagt.
