Exhibit 5.1

January 12, 2015

Paycom Software, Inc.

7501 W. Memorial Road

Oklahoma City, OK 73142

Ladies and Gentlemen:

We have acted as counsel to Paycom Software, Inc., a Delaware corporation (the “Company”), in connection with the preparation of the Company’s registration statement on Form S-1, Registration No. 333-201248 (the “Registration Statement”), under the Securities Act of 1933, as amended (the “Securities Act), initially filed by the Company with the Securities and Exchange Commission (the “Commission”) on December 23, 2014, as thereafter amended or supplemented. The Registration Statement relates to the sale by the selling stockholders listed in the Registration Statement (the “Selling Stockholders”) of shares of common stock, par value $0.01 per share (the “Common Stock”), of the Company proposed to be sold to the several underwriters (the “Underwriters”) named in Schedule I to the Underwriting Agreement (the “Underwriting Agreement”) to be entered into by and among the Company and the Underwriters, together with any additional shares of Common Stock proposed to be sold pursuant to an over-allotment option (the “Over-allotment Option”) granted by certain Selling Stockholders to the Underwriters named in the Underwriting Agreement (the “Shares”). The Selling Stockholders will sell in the aggregate up to 6,422,750 Shares, including the Over-allotment Option.

In rendering the opinion set forth herein, we have examined the originals, or photostatic or certified copies, of (i) the Amended and Restated Certificate of Incorporation and Amended and Restated By-Laws of the Company, each as amended and/or restated as of the date hereof; (ii) certain resolutions of the Board of Directors of the Company related to the filing of the Registration Statement, the authorization and issuance of the Shares and related matters; (iii) the Registration Statement and all exhibits included or incorporated by reference thereto; (iv) the form of Underwriting Agreement; (v) the specimen Common Stock certificate; (vi) a certificate executed by an officer of the Company, dated as of the date hereof; and (vii) such other records, documents and instruments as we deemed relevant and necessary for purposes of the opinion stated herein.

We have relied upon such certificates of officers of the Company and of public officials and statements and information furnished by officers of the Company with respect to the accuracy of material factual matters contained therein which were not independently established by us. In such examination we have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as photostatic or certified copies, and the authenticity of the originals of such copies.

We have not considered, and express no opinion herein as to, the laws of any state or jurisdiction other than the General Corporation Law of the State of Delaware, as currently in effect.

In rendering the opinion set forth below, we have assumed that, at the time of the issuance of the Shares, (i) the Registration Statement and any amendments thereto (including post-effective amendments) will have become effective and will remain effective; (ii) no stop order of the Commission preventing or suspending the use of the prospectus contained in the Registration Statement will have been issued; (iii) the prospectus contained in the Registration Statement and any required prospectus supplement will have been delivered to the purchaser of the Shares as required in accordance with applicable law; (iv) the

1

resolutions of the Board of Directors of the Company referred to above will not have been modified or rescinded; and (v) the Underwriting Agreement will have been duly authorized and validly executed and delivered by the parties thereto (other than the Company) and will be enforceable obligations of the parties thereto (other than the Company).

Based upon the foregoing, and subject to the qualifications, assumptions and limitations stated herein, we are of the opinion that the Shares are validly issued, fully paid and nonassessable.

We hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement. We further consent to the reference to our firm under the caption “Legal Matters” in the Prospectus constituting a part of the Registration Statement. In giving this consent, we are not admitting that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission.

Very truly yours,

/s/ Haynes and Boone, LLP

HAYNES AND BOONE, LLP

2