Exhibit 4.1

FIRST AMENDMENT TO RESTATED CREDIT AGREEMENT

THIS FIRST AMENDMENT TO RESTATED CREDIT AGREEMENT (this “Amendment”) is entered into as of June 14, 2013, by and between BARRETT BUSINESS SERVICES, INC., a Maryland corporation (“Borrower”), and WELLS FARGO BANK, NATIONAL ASSOCIATION (“Bank”).

RECITALS

WHEREAS, Borrower is currently indebted to Bank pursuant to the terms and conditions of that certain Restated Credit Agreement between Borrower and Bank dated as of November 1, 2012, as amended from time to time (“Credit Agreement”).

WHEREAS, Bank and Borrower have agreed to certain changes in the terms and conditions set forth in the Credit Agreement and have agreed to amend the Credit Agreement to reflect said changes.

NOW, THEREFORE, for valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties hereto agree that the Credit Agreement shall be amended as follows:

1. Section 1.3 of the Credit Agreement (captioned “STANDBY LETTERS OF CREDIT”) is hereby deleted in its entirety, and the following substituted therefor:

“SECTION 1.3. STANDBY LETTERS OF CREDIT.

(a) Standby Letters of Credit.

(i) Existing Standby Letters of Credit. Bank has issued or caused an affiliate to issue the following standby letters of credit (each an “Existing Standby Letter of Credit” and collectively, the “Existing Standby Letters of Credit”) for the account of Borrower, each of which was issued pursuant to the terms of that certain Standby Letter of Credit Agreement (Credit Agreement/Loan Agreement Version) between Bank and Borrower dated September 18, 2012 (as may be amended from time to time, the “Standby Letter of Credit Agreement”), and is outstanding as of the date hereof: (A) Standby Letter of Credit No. NZS401574 up to the aggregate amount of One Million Six Hundred Fifty Thousand Dollars ($1,650,000.00) dated June 21, 2001, as amended from time to time; (B) Standby Letter of Credit No. NZS504587 in the amount of Five Million Dollars ($5,000,000.00) dated December 8, 2003, as amended from time to time; (C) Standby Letter of Credit No. NZS568994 in the amount of Ten Thousand Dollars ($10,000.00) dated April 11, 2006; and (D) Irrevocable Standby Letter of Credit No. IS0013451 in the amount of Seventeen Million One Hundred Eighty Three Thousand Five Hundred Sixty-Seven Dollars ($17,183,567.00) dated July 11, 2012, as amended from time to time (the “Existing California SLOC”).

-1-

(ii) Amended Standby Letter of Credit. Subject to the terms of this Agreement, Bank hereby agrees to amend or cause an affiliate to amend the Existing California SLOC, for the account of Borrower and for the benefit of Borrower to secure Borrower’s workers’ compensation obligations to the State of California Self Insurance Plans to increase the principal amount thereof from Seventeen Million One Hundred Eighty Three Thousand Five Hundred Sixty-Seven and 00/100 Dollars ($17,183,567.00) to Sixty Three Million Nine Hundred Forty Three Thousand Eight Hundred Thirty Two and 00/100 Dollars ($63,943,832.00) (the “Amended California SLOC”). The form and substance of the Amended California SLOC shall be subject to approval by Bank, in its sole discretion.

(iii) Each Standby Letter of Credit shall remain subject to the additional terms of the Standby Letter of Credit Agreement, applications and any related documents required by Bank in connection with the issuance (and any renewal) thereof. Notwithstanding the provision of any Standby Letter of Credit regarding automatic extension of its expiration date, Bank may, at its sole option, give notice to the beneficiary thereof in accordance with the terms of such Standby Letter of Credit that Bank has elected not to renew such Standby Letter of Credit beyond its current expiration date (or any other subsequent expiration date that may be agreed to by Bank at Bank’s sole discretion). If Borrower does not at any time want any Standby Letter of Credit to be renewed, Borrower will so notify Bank at least fifteen (15) calendar days before Bank is to notify the beneficiary thereof of such nonrenewal pursuant to the terms of such Standby Letter of Credit. Subject to the terms and conditions of this Agreement and the Standby Letter of Credit Agreement, Bank hereby confirms that the Standby Letters of Credit remain in full force and effect. As used herein, “Standby Letter of Credit” means, individually, the Amended California SLOC or any of the Existing Standby Letters of Credit, and “Standby Letters of Credit” means, collectively, the Amended California SLOC and the Existing Standby Letters of Credit.

(b) Repayment of Drafts. Each drawing paid under any Standby Letter of Credit shall be repaid by Borrower in accordance with the provisions of the Standby Letter of Credit Agreement.”

-2-

2. Section 1.3 of the Credit Agreement (captioned “INTEREST/FEES”) is hereby amended by renumbering it as Section 1.4 of the Credit Agreement.

3. Section 1.4 of the Credit Agreement (captioned “COLLECTION OF PAYMENTS”) is hereby amended by renumbering it as Section 1.5 of the Credit Agreement.

4. Section 1.5 of the Credit Agreement (captioned “COLLATERAL”) is hereby deleted in its entirety, and the following substituted therefor:

“SECTION 1.6. COLLATERAL.

As security for all indebtedness and other obligations of Borrower to Bank, Borrower shall grant to Bank security interests of first priority in all Borrower’s accounts receivable and other rights to payment, general intangibles, inventory and equipment.

As security for all indebtedness and other obligations of Borrower to Bank under the Term Loan, Borrower shall grant to Bank a lien of not less than first priority on that certain real property located at 8100 NE Parkway Drive, Vancouver, Washington 98662 (the “Real Property”).

As security for all indebtedness and other obligations of Borrower to Bank under the Amended California SLOC, Borrower shall grant to Bank a security interest of first priority in deposit account number 1292505821 (the “Borrower Deposit Account”).

As security for all indebtedness and other obligations of Borrower to Bank under the Amended California SLOC, Borrower shall cause Associated Insurance Company for Excess, an Arizona corporation (“AICE”), to grant to Bank security interests of first priority in deposit account number 1292505789 (the “AICE Deposit Account”).

All of the foregoing shall be evidenced by and subject to the terms of such security agreements, financing statements, deeds or mortgages, and other documents as Bank shall reasonably require, all in form and substance satisfactory to Bank. Borrower shall pay to Bank immediately upon demand the full amount of all charges, costs and expenses (to include fees paid to third parties and all allocated costs of Bank personnel), expended or incurred by Bank in connection with any of the foregoing security, including without limitation, filing and recording fees and costs of appraisals, audits and title insurance.”

5. Section 4.3 of the Credit Agreement is hereby deleted in its entirety, and the following substituted therefor:

“SECTION 4.3. FINANCIAL STATEMENTS. Provide to Bank all of the following, in form and detail satisfactory to Bank:

(a) not later than 120 days after and as of the end of each fiscal year, an audited consolidated financial statement of Borrower, prepared by a certified public accountant acceptable to Bank, to include balance sheet, income statement, and statement of cash flows and sources, and shall be accompanied by the unqualified opinion of such accountant addressed to Bank;

-3-

(b) not later than 180 days after and as of the end of each fiscal year, an audited financial statement for each of AICE and Ecole Insurance Company, an Arizona corporation wholly owned by Borrower (“Ecole”) (AICE and Ecole, each an “Affiliate” and collectively, the “Affiliates”), prepared by a certified public accountant acceptable to Bank, to include balance sheet, income statement and statement of cash flows and sources, and shall be accompanied by the unqualified opinion of such accountant addressed to Bank;

(c) Promptly upon their becoming available, copies of (i) all financial statements, reports, notices and proxy statements made publicly available by Borrower to its security holders; (ii) all regular and periodic reports and all registration statements and prospectuses, if any, filed by Borrower with any securities exchange or with the U.S. Securities and Exchange Commission (“SEC”) or any governmental or private regulatory authority, including, but not limited to (A) not later than 95 calendar days after the end of each fiscal year, Borrower’s 10-K filing with the SEC (including all exhibits and certifications) for the fiscal year just ended, and (B) not later than 50 calendar days after the end of each fiscal quarter, Borrower’s 10-Q filing with the SEC (including all exhibits and certifications) for the fiscal quarter just ended; and (iii) all press releases and other statements made available by Borrower to the public concerning material changes or developments in the business of Borrower;

(d) contemporaneously with each annual and quarterly financial statement of Borrower and the Affiliates required hereby, a certificate of the president or chief financial officer of Borrower that said financial statements are accurate and that there exists no Event of Default nor any condition, act or event which with the giving of notice or the passage of time or both would constitute an Event of Default;

(e) annually, but in all events not later than October 15 of each year (commencing October 15, 2012), true and correct copies of a Uniform Certificate of Authority Application-Certificate of Compliance issued by the State of Arizona Director of Insurance for each of the Affiliates indicating that, as of a date no earlier than 30 days prior to the date each such certificate is delivered to Bank, each of the Affiliates is duly organized under the laws of the State of Arizona and authorized to transact the relevant insurance business of each of the Affiliates in the State of Arizona;

-4-

(f) annually, but in all events not later than April 30 of each year (commencing April 30, 2014), true and correct copies all third party actuarial reviews of the workers’ compensation obligations and liabilities of Borrower and the Affiliates, including such actuarial reviews of Borrower and the Affiliates provided to the State of California Self Insurance Plan; and

(g) from time to time such other information as Bank may reasonably request, including without limitation, copies of rent rolls and other information with respect to any real property collateral required hereby.”

6. The obligation of Bank to amend the terms and conditions of the Credit Agreement as provided herein is subject to the fulfillment to Bank’s satisfaction of all of the following conditions by no later than June 28, 2013:

(a) Bank shall have received, in form and substance satisfactory to Bank, each of the following, duly executed:

(b) Deposit Account Funds.

(i) Borrower shall have deposited into the Borrower Deposit Account, in immediately available funds, cash in an amount equal to Three Million Four Hundred Forty Three Thousand Eight Hundred Thirty Two and 00/100 Dollars ($3,443,832.00) as a time deposit for a period not less than three (3) months following the effective date of the Amended California SLOC.

(ii) Borrower shall have caused AICE to deposit into the AICE Deposit Account, in immediately available funds, cash in an amount equal to Sixty Million Five Hundred Thousand and 00/100 Dollars ($60,500,000.00) as a time deposit for a period not less than three (3) months following the effective date of the Amended California SLOC.

(c) Other Fees and Costs. In addition to Borrower’s obligations under the Credit Agreement and the other Loan Documents, Borrower shall have paid to Bank the full amount of all costs and expenses, including reasonable attorneys’ fees (including the allocated costs of Bank’s in-house counsel) expended or incurred by Bank in connection with the negotiation and preparation of this Amendment, for which Bank has made demand.

-5-

7. Borrower covenants and agrees that for so long as the Amended California SLOC remains outstanding: (a) Borrower shall maintain in full force and effect, and pay all premiums with respect to, all policies of insurance with AICE outstanding as of the date hereof with respect to the satisfaction of Borrower’s worker’s compensation obligations under the laws of the State of California (the “AICE Policies”); (b) Borrower shall not terminate or cancel any of the AICE Policies without Bank’s prior written consent; and (c) in the event any of the AICE Policies are terminated or cancelled for any reason, Borrower shall promptly cause all premiums refunded therefrom to be deposited into the Borrower Deposit Account.

8. Except as specifically provided herein, all terms and conditions of the Credit Agreement remain in full force and effect, without waiver or modification. All terms defined in the Credit Agreement shall have the same meaning when used in this Amendment. This Amendment and the Credit Agreement shall be read together, as one document.

9. Borrower hereby remakes all representations and warranties contained in the Credit Agreement and reaffirms all covenants set forth therein. Borrower further certifies that as of the date of this Amendment there exists no Event of Default as defined in the Credit Agreement, nor any condition, act or event which with the giving of notice or the passage of time or both would constitute any such Event of Default.

UNDER OREGON LAW, MOST AGREEMENTS, PROMISES AND COMMITMENTS MADE BY BANK CONCERNING LOANS AND OTHER CREDIT EXTENSIONS WHICH ARE NOT FOR PERSONAL, FAMILY OR HOUSEHOLD PURPOSES OR SECURED SOLELY BY THE BORROWER’S RESIDENCE MUST BE IN WRITING, EXPRESS CONSIDERATION AND BE SIGNED BY BANK TO BE ENFORCEABLE.

-6-

IN WITNESS WHEREOF, the parties hereto have caused this Amendment to be executed as of the day and year first written above.

-7-