The seasonally adjusted number was shy of the 60,000 new jobs expected by most analysts.
But ADP revised sharply higher the April jobs gain, to 65,000, from its original estimate of 32,000.
According to ADP, the service sector, which accounts for about 70 percent of output in the worlds largest economy, spawned 78,000 jobs in May, the fourth month running of increases.
The goods-producing sector saw the only decline in employment, shedding 23,000 jobs.
The average increase over the past four months was a modest 39,000, said Joel Prakken, chairman of Macroeconomic Advisors, ADPs partner in the report.
The slow pace of improvement from February through May is consistent with the pause in the decline of initial unemployment claims that occurred during the winter months, he said.
The ADP private payrolls report came ahead of the highly anticipated government jobs report Friday, which also includes government hiring.
Most analysts expected the Labor Department will report 500,000 nonfarm jobs were created last month, up from 290,000 in April, and the unemployment rate slipped a notch to 9.8 percent from 9.9 percent.
Analysts said the expected surge in new jobs would come mostly from temporary government hiring for the 2010 census.
President Barack Obama said Wednesday he expects a strong May jobs report.
The president, who has made job creation a top administration priority in getting the government-fueled recovery on a sustainable path, noted the economy had added jobs for five of the past six months.
We... expect to see strong job growth on Fridays report, he said.
Meanwhile, new orders to US factories rose less than expected in April, with the increase led by a jump in civilian aircraft orders, official data showed Thursday.
Orders for manufactured goods increased 1.2 percent from March after an upwardly revised 1.7 percent gain in April, the Commerce Department said.
New orders have increased in 12 of the past 13 months. The April figure was below the average analyst forecast of a 1.7 percent rise.
Excluding new orders for transportation goods, which can vary widely from month to month, factory orders fell 0.5 percent after a 3.8 percent increase in March.
Commercial aircraft orders soared 228.1 percent.
The Commerce Department also said April orders for durable goods big-ticket items expected to last a few years were slightly lower than originally estimated, at 2.8 percent instead of 2.9 percent.
Overall, orders of manufactured goods have increased 15.6 percent in the year to date as the manufacturing sector leads the economy out of the worst recession in decades.
Meanwhile, the US service sector grew for the fifth consecutive month in May, holding steady at the same pace of expansion for the last three months, an industry survey showed Thursday.
The Institute for Supply Management said its monthly survey found a mostly positive outlook among purchasing and supply managers in the vast service sector, which accounts for about 70 percent of US economic activity.
The ISM said its non-manufacturing index stood at 55.4 percent in May, the same percentage as in March and April. A reading above 50 indicates expansion.
Respondents comments remain mostly positive about current business conditions and the general direction of the economy, said Anthony Nieves, chair of the ISM non-manufacturing survey committee.
The flat growth was a shade below the average analyst forecast of 55.6 percent.
Although the headline came in slightly below expectations, this is a positive report, which shows continued growth in the service sector, said Nicholas Tenev at Barclays Capital.
The components of the survey were mixed. The ISM index on business activity in the service sector rose for the sixth month in a row, to 61.1 from 60.3 in April.
The index on new orders slipped 1.1 percentage points to 57.1 percent, while the prices index fell 4.1 percentage points to 60.6 percent, showing prices increases were slowing.
The ISM report offered a ray of hope for the ailing jobs market as the economy struggles with a high unemployment rate amid a slow recovery from severe recession.
The employment index increased 0.9 percentage point to 50.4 percent, the first growth after 28 consecutive months of contraction. Overall, the results are consistent with a broadening in the base of growth with little negative impact on demand from recent financial market turmoil, said Moodys Economy.com analyst Aaron Smith. The service sector report was not as strong as the ISM index on the manufacturing sector released Tuesday, which stood at 59.7 percent in May, down from 60.4 percent in April.