Exhibit 5.1

March 31, 2014

Paycom Software, Inc.

7501 W. Memorial Road

Oklahoma City, OK 73142

Re:   Paycom Software, Inc.

  Registration Statement on Form S-1, Registration No. 333-194462

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-194462 (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 March 10, 2014, as thereafter amended or supplemented. The Registration Statement relates to (a) the issuance by the Company of shares of common stock, par value $0.01 per share (the “Common Stock”), 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 (the “Company Shares”), and (b) the sale by the selling stockholders listed in the Registration Statement (the “Selling Stockholders”) of shares of Common Stock of the Company proposed to be sold to the Underwriters named in the Underwriting Agreement, together with any additional shares of Common Stock proposed to be sold pursuant to an over-allotment option (the “Over-allotment Option”) granted by the Selling Stockholders to the Underwriters named in the Underwriting Agreement (the “Selling Stockholder Shares” and, together with the Company Shares, the “Shares”). The Company and the Selling Stockholders will sell in the aggregate up to 7,641,750 Shares, including the Over-allotment Option.

In rendering the opinions 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 and related matters; (iii) the Registration Statement and all exhibits 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 (the “DGCL”).

In rendering the opinion set forth below, we have assumed that, at the time of the issuance of the Shares, (i) the Company will continue to be incorporated and in existence and good standing under the DGCL; (ii) the Registration Statement and any amendments thereto (including post-effective amendments) will have become effective and will remain effective; (iii) no stop order of the Commission preventing or suspending the use of the prospectus contained in the Registration Statement will have been issued; (v) 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; (vi) the resolutions of the Board of Directors of the Company referred to above will not have been modified or rescinded; (vii) the Company will receive consideration for the issuance of the Shares that is at least equal to the par value of the Common Stock; (viii) the stock certificates (if any) representing the Shares will comply with the provisions of Delaware Law, the Amended and Restated Certificate of Incorporation and Amended and Restated By-laws of the Company when the Shares are issued; (ix) all Shares will be issued in compliance with applicable federal, state and other laws and in the manner stated in the Registration Statement, or any amendment thereto, along with any applicable prospectus supplement; and (x) 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 (1) upon payment and delivery in accordance with the Underwriting Agreement approved by the Pricing Committee of the Board of Directors of the Company (the “Pricing Committee”) and the Selling Stockholders, the Company Shares will be validly issued, fully paid and nonassessable and (2) upon payment and delivery in accordance with the Underwriting Agreement approved by the Pricing Committee and the Selling Stockholders, the Selling Stockholders Shares will be 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