Description of Business, Basis of Presentation, and Significant Accounting Policies (Narrative) (Details) $ / shares in Units, $ in Millions	12 Months Ended
	May 31, 2016 USD ($) segment $ / shares	May 31, 2015 USD ($)	May 31, 2014 USD ($)	Jul. 07, 2016 $ / shares
Accounting Policies [Line Items]
Number of reportable segments | segment	1
Maximum period in which payroll taxes will be remitted after receipt of collections from clients	90 days
Declared date	Jul. 07, 2016
Quarterly dividend per share | $ / shares	$ 0.42
Payable date	Aug. 25, 2016
Record date	Aug. 01, 2016
Allowance for doubtful accounts	$ 4.2	$ 1.4
Accounts receivable, net of allowance for doubtful accounts	408.6	176.6
Goodwill	657.1	561.5
Goodwill impairment loss	0.0	0.0	$ 0.0
Direct pass-through costs	5,100.0	4,200.0	$ 3,400.0
Maximum individual workers' compensation claims liability	1.3	1.0
Workers' compensation insurance costs in current liabilities	13.8	11.3
Workers' compensation insurance costs in long-term liabilities	18.4	15.3
Maximum individual health insurance claims liability	0.3	0.3
PEO accrued health insurance reserves in current liabilities	9.5	8.1
Reserve for uncertain tax positions	$ 54.2	29.1
Software Development [Member]
Accounting Policies [Line Items]
Estimated useful lives	15 years
Minimum [Member]
Accounting Policies [Line Items]
Period in which payroll taxes are typically remitted after receipt of collections from clients	1 day
Payroll funding fees average collection period	45 days
Amortization period	3 years
Minimum [Member] | Software [Member]
Accounting Policies [Line Items]
Estimated useful lives	3 years
Maximum [Member]
Accounting Policies [Line Items]
Period in which payroll taxes are typically remitted after receipt of collections from clients	30 days
Payroll funding fees average collection period	60 days
Amortization period	12 years
Maximum [Member] | Software [Member]
Accounting Policies [Line Items]
Estimated useful lives	5 years
Trade Receivables [Member]
Accounting Policies [Line Items]
Accounts receivable, net of allowance for doubtful accounts	$ 221.6	$ 176.6
Purchased Receivables [Member]
Accounting Policies [Line Items]
Accounts receivable, net of allowance for doubtful accounts	$ 187.0
Germany [Member] | Total Revenue [Member] | Geographic Concentration Risk [Member]
Accounting Policies [Line Items]
Percentage of total revenue less than one percent	1.00%	1.00%	1.00%
Subsequent Event [Member]
Accounting Policies [Line Items]
Quarterly dividend per share increase | $ / shares				$ 0.04
Quarterly dividend percentage increase				10.00%
Quarterly dividend per share | $ / shares				$ 0.46