The high-flying Falcons led 15-8 at half-time after May's try from 40m out and a push-over score for Andy Long cancelled out Joe Bedford's early try.
Two penalties from Leeds' Leigh Hinton to a Matt Burke drop-goal gave Falcons an 18-14 lead in the last quarter.
Leeds' Eric Lund crashed over with 11 minutes left but May snatched the win.
Falcons director of rugby John Fletcher:
"Players are paid to win matches and I'll take a win any time. "I was very happy with our first-half performance, but the second half was not so good. We started badly and just got worse.
"They defended well and we just could not keep the ball, panicked a bit and lost our shape, but I felt we showed real character when Phil Dowson and Matt Burke were off the field to set up the drop-goal for Tom May.
"We have actually been practising drop-goals in training all week because I think it is the easiest way to score."
Newcastle: Burke; May, Mayerhofler, Shaw, Rudd; Jones, Dickson; McDonnell, Long, Wilson, Oakes, Sorenson, Parling, Dowson (capt), Winter.
. Replacements:Thompson, Golding, Perry, Wilson, Grindal, Dehaty, Phillips.
Leeds: Hinton; Holtby, Rock, Blackett, Biggs; Vasey, Bedford; McGee, Ma'asi, Noon, E Lund, Hooper (capt), Oakley, Clark, Lock.
Replacements: Cusack, Parkes, Bouza, Myall, Aspinall, Satala, Goodridge.
E-mail this to a friend 
Printable version 
Bookmark with:
What are these?