Exhibit 5.1

April 27, 2012

Kforce Inc.

1001 East Palm Avenue

Tampa, Florida 33605

Re: Kforce Inc. Registration Statement on Form S-3

Ladies and Gentlemen:

We have acted as counsel to Kforce Inc., a Florida corporation (the “Company”), in connection with the registration statement on Form S-3 to be filed on the date hereof by the Company (the “Registration Statement”) with the U.S. Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Act”). The Registration Statement relates to the issuance and sale by the Company from time to time, pursuant to Rule 415 of the rules and regulations promulgated under the Act, of an unspecified amount of securities of the Company, consisting of: (i) shares of common stock of the Company, $0.01 par value per share (the “Common Stock”); (ii) shares of preferred stock of the Company, $0.01 par value per share, to be issued in one or more series (the “Preferred Stock”); (iii) debt securities (the “Debt Securities”) to be issued in one or more series under the indenture proposed to be entered into between the Company and a financial institution to be named therein, as trustee, the form of which is filed as an exhibit to the Registration Statement (the “Indenture”); (iv) warrants (the “Warrants”) to purchase Debt Securities, Common Stock, Preferred Stock, Depositary Shares (as defined herein), Units (as defined herein) or any combination of these securities as shall be designated by the Company at the time of the offering issued pursuant to one or more warrant agreements (each, a “Warrant Agreement”) proposed to be entered into between the Company and warrant agents to be named; (v) depositary shares each representing a fraction of a share of Preferred Stock (the “Depositary Shares”), evidenced by depositary receipts (the “Depositary Receipts”), which may be issued pursuant to one or more deposit agreements (each a “Deposit Agreement”) to be entered into between the Company and a depositary to be named therein (each a “Depositary”); and (vi) units consisting of Common Stock, Preferred Stock, Debt Securities, and/or Warrants (the “Units”) issued under one or more unit agreements (each a “Unit Agreement”) to be entered into between the Company and a bank or other financial institution, as unit agent. The Common Stock, Preferred Stock, Debt Securities, Warrants, Depositary Shares and Units are collectively referred to herein as the “Offered Securities.” The proposed maximum aggregate public offering price of the Offered Securities to be sold by the Company is $250,000,000, on terms to be determined at the time of the offering thereof. In addition to the Offered Securities, the Company’s selling shareholders named in the Registration Statement (the “Selling Shareholders”) have registered 6,188,285 shares of Common Stock for resale.

This opinion is being delivered in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Act.

In connection with this opinion, we have examined originals or copies, certified or otherwise identified to our satisfaction, of:

i. the Registration Statement;

ii. the form of the Indenture; and

iii. certain resolutions adopted by the board of directors of the Company (the “Board of Directors”) relating to the registration of the Offered Securities and related matters.

We have also examined originals or copies, certified or otherwise identified to our satisfaction, of such records of the Company and such agreements and certificates of public officials, certificates of officers or other representatives of the Company and others, and such other documents, as we have deemed necessary or appropriate as a basis for the opinions set forth below.

As to any facts material to the opinions expressed herein which were not independently established or verified, we have relied upon oral or written statements and representations of officers and other representatives of the Company and others.

The opinions expressed below are limited to the laws of the State of Florida and the federal laws of the United States (the “Applicable Law”). Therefore, we express no opinion concerning matters governed by the laws of any other jurisdictions or the effects of such laws upon the transactions of the type covered by the Registration Statement. To the extent that any matter discussed below is governed by the laws of other jurisdictions, we have assumed without analysis that the conclusion under governing law would be the same as that under Florida law. The Offered Securities may be issued from time to time on a delayed or continuous basis, and this opinion is limited to the laws, including the rules and regulations, as in effect on April 27, 2012, the date of this letter, which laws are subject to change with possible retroactive effect.

Based upon and in reliance on the documents and representations referred to above and subject to the foregoing, we are of the opinion that:

1. With respect to any series of Common Stock to be offered by the Company pursuant to the Registration Statement (the “Offered Common Stock”), when: (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act, (ii) an appropriate prospectus supplement with respect to the Offered Common Stock has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder, (iii) if the Offered Common Stock is to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to the Offered Common Stock has been duly authorized, executed and delivered by the Company and the other parties thereto, (iv) the Board of Directors, including any appropriate committee appointed thereby, and appropriate officers of the Company have taken all necessary corporate action (including obtaining shareholder approval, if necessary) to approve the issuance and terms of the Offered Common Stock and related matters, (v) the Offered Common Stock has been issued and delivered so as not to violate any Applicable Law, the Amended and Restated Articles of Incorporation, as amended to date (the “Articles of Incorporation”), or the Amended and Restated Bylaws (the “Bylaws”), or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, and (vi) the certificates of the Offered Common Stock have been duly executed by the Company, countersigned by the transfer agent therefor and duly delivered to the purchasers thereof against payment in full therefor, then the Offered Common Stock (including any as part of any Units), when issued and sold as contemplated in the Registration Statement and the appropriate prospectus supplement and in accordance with any applicable duly authorized, executed and delivered purchase, underwriting or similar agreement, or upon conversion of any convertible Preferred Stock or convertible Debt Securities in accordance with their terms, or upon exercise of any Warrants in accordance with their terms, will have been duly authorized and validly issued and will be fully paid and non-assessable.

2. With respect to any series of Preferred Stock to be offered by the Company pursuant to the Registration Statement (the “Offered Preferred Stock”), when: (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act, (ii) an appropriate prospectus supplement with respect to the Offered Preferred Stock has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder, (iii) if the Offered Preferred Stock is to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to the Offered Preferred Stock has been duly authorized, executed and delivered by the Company and the other parties thereto, (iv) the Board of Directors, including any appropriate committee appointed thereby, and appropriate officers of the Company have taken all necessary corporate action (including obtaining shareholder approval, if necessary) to approve the issuance and terms of the Offered Preferred Stock and related matters, (v) the Offered Preferred Stock has been issued and delivered so as not to violate any Applicable Law, the Articles of Incorporation, or the Bylaws, or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, (vi) Articles of Amendment to the Company’s Articles of Incorporation that comply with Florida Statutes Section 607.0602(4), have been duly filed with the Secretary of State of the State of Florida, (vii) the certificates of Preferred Stock have been duly executed by the Company, countersigned by the transfer agent therefor and duly delivered to the purchasers thereof against payment in full therefor and (viii) the Common Stock relating to such

2

Offered Preferred Stock has been duly authorized for issuance (if such Offered Preferred Stock is convertible to Common Stock), then the Offered Preferred Stock (including any as part of any Units), when issued and sold as contemplated in the Registration Statement and the appropriate prospectus supplement and in accordance with any applicable duly authorized, executed and delivered purchase, underwriting or similar agreement, or upon conversion of any convertible Debt Securities in accordance with their terms, or upon exercise of any Warrants in accordance with their terms, will have been duly authorized and validly issued and will be fully paid and non-assessable.

3. With respect to any series of Debt Securities to be offered by the Company pursuant to the Registration Statement (the “Offered Debt Securities”), when: (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act and the Indenture has been qualified under the Trust Indenture Act, (ii) an appropriate prospectus supplement with respect to any Offered Debt Securities has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder, (iii) if the Offered Debt Securities are to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to the Offered Debt Securities has been duly authorized, executed and delivered by the Company and the other parties thereto, (iv) the Board of Directors, including any appropriate committee appointed thereby, and appropriate officers of the Company have taken all necessary corporate action (including obtaining shareholder approval, if necessary) to approve the issuance and terms of the Offered Debt Securities and related matters, (v) the Indenture and any supplemental indenture with respect to such Offered Debt Securities have been duly authorized, executed and delivered by each party thereto, (vi) the terms of the Offered Debt Securities and of their issuance and sale have been duly established in conformity with the Indenture and any supplemental indenture to be entered into in connection with the issuance of such Offered Debt Securities so as not to violate any Applicable Law, the Articles of Incorporation or the Bylaws of the Company, or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, (vii) the Common Stock or the Preferred Stock relating to such Offered Debt Securities that are convertible have been duly authorized for issuance, and (viii) the Offered Debt Securities have been issued in a form that complies with the Indenture and have been duly executed and authenticated in accordance with the provisions of the Indenture and any supplemental indenture to be entered into in connection with the issuance of such Offered Debt Securities and duly delivered to the purchasers thereof upon payment of the agreed-upon consideration therefor, then the Offered Debt Securities (including any Debt Securities duly issued upon conversion, exchange or exercise of any Preferred Stock, Debt Securities, or Warrants, as applicable, or any Debt Securities that are part of any Units), when issued and sold in accordance with the Indenture and any supplemental indenture to be entered into in connection with the issuance of such Debt Securities and the applicable underwriting agreement, if any, or any other duly authorized, executed and delivered valid and binding purchase or agency agreement, will be valid and binding obligations of the Company, enforceable against the Company in accordance with their respective terms.

4. With respect to any series of Warrants to be offered by the Company pursuant to the Registration Statement (the “Offered Warrants”), when: (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act, (ii) an appropriate prospectus supplement with respect to the Offered Warrants has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder, (iii) if the Offered Warrants are to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to the Offered Warrants has been duly authorized, executed and delivered by the Company and the other parties thereto, (iv) the Board of Directors, including any appropriate committee appointed thereby, and appropriate officers of the Company have taken all necessary corporate action (including obtaining shareholder approval, if necessary) to approve the issuance and terms of the Offered Warrants, the Warrant Agreement and related matters, (v) the applicable Warrant Agreement has been duly authorized, executed and delivered by each party thereto, (vi) the terms of the Offered Warrants and of their issuance and sale have been duly established in conformity with the applicable Warrant Agreement so as not to violate any Applicable Law, the Articles of Incorporation or Bylaws or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, (vii) the Common Stock, the Preferred Stock or the Debt Securities relating to such Offered Warrants have been duly authorized for issuance, and (viii) the Offered Warrants have been duly executed, delivered, countersigned, issued and sold in accordance with the provisions of the applicable Warrant Agreement to be filed on a Current Report on Form 8-K in the manner contemplated in the Registration Statement or any amendment relating thereto, then the Offered Warrants (including any as part of any Units), when issued and sold in accordance with the applicable Warrant Agreement and the

3

applicable underwriting agreement, if any, or any other duly authorized, executed and delivered valid and binding purchase or agency agreement, will be valid and binding obligations of the Company, enforceable against the Company in accordance with their respective terms.

5. With respect to any Depositary Shares to be offered by the Company pursuant to the Registration Statement (the “Offered Depositary Shares”), when: (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act, (ii) an appropriate prospectus supplement with respect to the Offered Depositary Shares has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder, (iii) if the Offered Depositary Shares are to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to the Offered Depositary Shares has been duly authorized, executed and delivered by the Company and the other parties thereto, (iv) the Board of Directors, including any appropriate committee appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance and terms of the Offered Depositary Shares and the related series of Preferred Stock, the applicable Deposit Agreement and related matters, (v) the applicable Deposit Agreement has been duly authorized, executed and delivered by each party thereto, (vi) the terms of the Offered Depositary Shares and their issuance and sale have been duly established in conformity with the applicable Deposit Agreement so as not to violate any Applicable Law, the Articles of Incorporation or the Bylaws, or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, (vii) the Preferred Stock relating to such Offered Depositary Shares have been duly authorized for issuance, and (viii) the Depositary Receipts, a form of which shall be filed on a Current Report on Form 8-K in the manner contemplated in the Registration Statement or any amendment relating thereto, evidencing the Depositary Shares have been duly issued against deposit of the related shares of Preferred Stock with the Depositary in accordance with the applicable Deposit Agreement, then the Depositary Shares, when issued and sold in accordance with the applicable Deposit Agreement and the applicable underwriting agreement, if any, or any other duly authorized, executed and delivered valid and binding purchase or agency agreement will be validly issued and the Depositary Receipts will entitle the holders thereof to the rights specified therein and in the Deposit Agreement.

6. With respect to any Units to be offered by the Company pursuant to the Registration Statement (the “Offered Units”), when: (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act, (ii) an appropriate prospectus supplement with respect to the Offered Units has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder, (iii) if the Offered Units are to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to the Offered Units has been duly authorized, executed and delivered by the Company and the other parties thereto, (iv) the Board of Directors, including any appropriate committee appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance and terms of the Offered Units, the applicable Unit Agreement and related matters, (v) the applicable Unit Agreement has been duly authorized, executed and delivered by each party thereto, (vi) the terms of the Offered Units and of their issuance and sale have been duly established in conformity with the Unit Agreement so as not to violate any Applicable Law, the Articles of Incorporation or the By-Laws, or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, (vii) the Common Stock, Preferred Stock, Debt Securities and/or Warrants relating to such Offered Units have been duly authorized for issuance, and (viii) the applicable Offered Units have been duly executed, delivered, countersigned, issued and sold in accordance with the provisions of the applicable Unit Agreement to be filed on a Current Report on Form 8-K in the manner contemplated in the Registration Statement or any amendment relating thereto, then the Offered Units, when issued and sold in accordance with the applicable Unit Agreement and the applicable underwriting agreement, if any, or any other duly authorized, executed and delivered valid and binding purchase or agency agreement, will be valid and binding obligations of the Company, enforceable against the Company in accordance with their respective terms.

7. The Selling Shareholder shares have been validly issued and are fully paid and non-assessable.

In rendering the opinions set forth above, we have assumed that:

i. the consideration paid for any Offered Common Stock or Offered Preferred Stock will comply with Florida Statutes, Section 607.0621 (2), (3) and (4) or any successor provision;

4

ii. any amendment to the Articles of Incorporation in respect of any Offered Preferred Stock will be in conformity with the Articles of Incorporation and Bylaws of the Company and with Applicable Law;

iii. after the issuance of the Offered Common Stock, the total number of issued shares of Common Stock, together with the total number of shares of Common Stock reserved for issuance upon the exercise, exchange or conversion, as the case may be, of any exercisable, exchangeable or convertible security, or any stock option or warrant, as the case may be, then outstanding, will not exceed the total number of authorized shares of Common Stock under the Company’s Articles of Incorporation; and

iv. after the issuance of the Offered Preferred Stock, the total number of issued shares of Preferred Stock, together with the total number of shares of Preferred Stock reserved for issuance upon the exercise, exchange or conversion, as the case may be, of any exercisable, exchangeable or convertible security, or any stock option or warrant, as the case may be, then outstanding, will not exceed the total number of authorized shares of Preferred Stock under the Company’s Articles of Incorporation.

Our opinions set forth above are subject to the effects of (i) bankruptcy, insolvency, fraudulent conveyance, fraudulent transfer, reorganization and moratorium laws, and other similar laws relating to or affecting creditors’ rights or remedies generally, (ii) general equitable principles (whether considered in a proceeding in equity or at law) and (iii) concepts of good faith, reasonableness and fair dealing, and standards of materiality.

We hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement. We also consent to the reference to our firm under the caption “Legal Matters” in the prospectus which forms a part of the Registration Statement. In giving this consent, we do not thereby admit that we are included in the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission promulgated thereunder. This opinion is expressed as of the date hereof, and we disclaim any undertaking to advise you of any subsequent changes in the facts stated or assumed herein or of any subsequent changes in Applicable Law.

Very truly yours,

/s/ Holland & Knight LLP

5