BOARD NOMINATION AND OBSERVER AGREEMENT

Exhibit 10.4

BOARD NOMINATION AND OBSERVER AGREEMENT

This Board Nomination and Observer Agreement (this “Agreement”) is made as of September 25, 2012, among Authentidate Holding Corp., a Delaware corporation (the “Company”) and Lazarus Investment Partners, LLLP, a limited liability partnership (the “Stockholder”). Unless otherwise specified herein, all of the capitalized terms used herein are defined in Section 5 hereof.

WHEREAS, the Company has entered into a Securities Purchase Agreement, dated as of September 24, 2012 (the “Purchase Agreement”), with the Stockholder and the other parties identified on Schedule I thereto whereby the Stockholder has agreed to participate in transaction described therein; and

WHEREAS, the Company has agreed to grant the Stockholder, subject to the limitations set forth in this Agreement, to observation and nomination rights as set forth herein on the terms and conditions of this Agreement.

NOW, THEREFORE, in consideration of the mutual covenants contained herein and other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties to this Agreement hereby agree as follows:

Section 1. Board Observer Rights.

(a) At any time prior to the Expiration Time, provided that the Stockholder has not exercised its rights under Section 2 of this Agreement and such Stockholder together with its Affiliates Beneficially Own 5.0% or greater of the Outstanding Equity, the Stockholder may designate a Board observer reasonably acceptable to the Company (the “Board Observer”) to attend all meetings of the Board, in a non-voting capacity, by the giving of written notice to the Company’s Chairman or Chief Executive Officer of such designation (“Observation Election”) prior to the Expiration Time. In connection therewith and during the time period set forth in Section 1(b), the Company shall simultaneously give the Board Observer copies of all notices, consents, minutes and other materials, financial or otherwise, which the Company provides to the Board in connection with meetings of the Board to be held during such time frame, provided that (i) if the Board Observer does not, upon the request of the Company, before attending any meetings of the Board, execute and deliver to the Company a confidentiality agreement reasonably acceptable to the Company, the Board Observer may be excluded from access to any material or meeting or portion thereof if the Board determines in good faith that such exclusion is reasonably necessary to protect confidential proprietary information of the Company or confidential proprietary information of third parties that the Company is required to hold in confidence, or for other similar reasons; (ii) such representative may be excluded from access to any material or meeting or portion thereof if the Board determines in good faith that such exclusion is reasonably necessary to preserve the attorney-client privilege; (iii) any committee of the Board may exclude the Observer from attending any meeting of such committee in its discretion; and (iv) nothing herein shall prohibit the Board or any committee of the Board from taking any action proposed to be taken at any meeting of the Board or committee or by written consent.

(b) In the event the Stockholder makes an Observation Election, the Stockholder shall have the observation rights set forth herein for a period of time expiring on the earlier of (i) the second anniversary date of the Effective Date, (ii) the date on which the Stockholder makes an election to appoint a Nominee in accordance with Section 2 of this Agreement, or (iii) the occurrence of a General Termination Event. All obligations of the Company pursuant to this Section 1 shall terminate upon the Stockholder ceasing to have the right to designate a Board Observer pursuant to this Section 1.

- 1 -

(c) Stockholder agrees, and Stockholder will cause any Board Observer to agree, to hold in confidence with respect to all information so provided and not use or disclose any confidential information provided to or learned by it in connection with its rights under this Agreement other than for purposes reasonably related to its interest as a shareholder of the Company, and not to the detriment of, the Company. The confidentiality provisions hereof will survive any termination of this Agreement. The Stockholder shall cause the Board Observer to agree to, and shall be responsible for the Board Observer’s failure to, hold in confidence and trust and to act in a fiduciary manner with respect to all information provided to such Board Observer pursuant hereto.

Section 2. Board Nomination Rights.

(a) At any time prior to the Expiration Time, subject to the terms and conditions of this Agreement and provided that the Stockholder together with its Affiliates Beneficially Own 10.0% or greater of the Outstanding Equity, the Stockholder shall have the right (but not the obligation) to designate one person to be nominated for election to the Board (a “Nominee”) by giving written notice to the Chairman of the Board or the Secretary of the Company prior to the Expiration Time. As a condition of exercising its right under Section 2 of this Agreement, the Stockholder hereby agrees that effective upon the election of such Nominee to the Board, the Stockholder’s rights under Section 1 of this Agreement shall automatically expire and no person may continue to act in the capacity as Board Observer. The Nominee shall be selected by the Stockholder in reasonable consultation with (but without the need for the approval of) the Company’s Nominating and Corporate Governance Committee of its Board of Directors (the “Nominating Committee”).

(b) Provided the Stockholder exercises its right under Section 2(a) prior to the Expiration Time, the Company shall subject to its rights under Section 3: (i) promptly increase the size of the Board from five (5) to six (6) members; (ii) appoint such Nominee as a member of the Board; and (iii) at all times during the Designation Period, include, and shall use its best efforts to cause the Board, whether acting through the Nominating and Corporate Governance Committee of the Board or otherwise, to include the Nominee in the slate of nominees recommended to the Stockholders for election as a director at any annual or special meeting of the Stockholders held during the Designation Period (or, if permitted, by any action by written consent of the Stockholders taken during the Designation Period) at or by which directors of the Company are to be elected.

(c) If a Board vacancy occurs during the Designation Period solely because of the death, disability, disqualification, resignation or removal of the Nominee, the Stockholder shall be entitled to designate such person’s successor in accordance with Section 3(b).

(d) If during the Designation Period the Nominee is not nominated or elected to the Board because of such Nominee’s death, disability, disqualification, withdrawal as a nominee or such Nominee is for any other reason unavailable or unable to serve on the Board, the Stockholder shall be entitled to promptly designate another Nominee in accordance with the applicable provisions of Section 2 and the director position for which such Nominee was nominated shall not be filled pending such designation.

(e) A Nominee shall be entitled to the same compensation paid and expense reimbursement payable to other non-employee Directors.

(f) If in the reasonable judgment of the Company, the election or appointment of the Nominee would cause the Company to not comply with the relevant listing rules of the Nasdaq Stock Market (the “Listing Rules”), including the requirement that the Company’s Board be comprised of a majority of Independent Directors, then the Company may defer the appointment and/or election of such

- 2 -

Nominee until it is able to take commercially reasonable measures to ensure that such appointment or election would not cause the Company to violate the Listing Rules. For the purpose of clarity, it is agreed that such measures may include a further increase in the size of the Board and the appointment and/or election of an additional individual to serve as an Independent Director, which individual shall be selected in the sole discretion of the Company.

(g) For the avoidance of doubt, the provisions of this Agreement shall not limit any rights the Stockholder may have as a stockholder of the Company pursuant to Delaware law, the Certificate of Incorporation or the By-Laws.

Section 3. Company Obligations.

(a) Notwithstanding anything herein to the contrary, the Company shall not be obligated to appoint any Nominee to serve on the Board or cause to be nominated for election to the Board or recommend to the stockholders the election of any Nominee: (i) who fails to submit to the Company on a timely basis such questionnaires as the Company may reasonably require of its directors generally and such other information as the Company may reasonably request in connection with the preparation of its filings under the Securities Laws; or (ii) if the Board or the Nominating Committee (if any) determines in good faith, after consultation with outside legal counsel, that (A) such action would constitute a breach of its fiduciary duties or applicable law or violate the Company’s Certificate of Incorporation or By-Laws; or (B) such Nominee would not be qualified under any applicable law, rule or regulation to serve as a Director of the Company; provided, however, that upon the occurrence of either (i) or (ii) above, the Company shall promptly notify the Stockholder of the occurrence of such event and permit the Stockholder to provide an alternate Nominee sufficiently in advance of any Board action, the meetings of the stockholders called or written action of stockholders with respect to such election of nominees and the Company shall use commercially reasonable efforts to perform its obligations under Section 2 with respect to such alternate Nominee (provided that if the Company provides at least 45 days advance notice of the occurrence of any such event such alternative nominee must be designated by the Stockholder not less than 30 days in advance of any Board action, notice of meeting of the stockholders or written action of stockholders with respect to such election of nominees), and in no event shall the Company be obligated to postpone, reschedule or delay any scheduled meeting of the stockholders with respect to such election of Nominees.

(b) If at any time during Designation Period a Board vacancy occurs solely because of the death, disability, disqualification, resignation or removal of the Nominee, then the Board, or any committee thereof, shall not fill such vacancy until the earliest to occur of: (i) the Stockholder’s designation of a successor Nominee (which successor Nominee shall be designated in accordance with Section 2(a) and subject to the terms of Section 3(a)) and the Board’s appointment of such successor Nominee to fill the vacancy; (ii) the Stockholder’s failure to designate a successor Nominee within 20 Business Days after receiving notification of the vacancy from the Company; or (iii) the Stockholder’s specifically waiving in writing its rights under this Section 3(b). For the purposes of clarity, the Company shall have the right to fill any Board vacancy which may occur due to any reason other than the death, disability, disqualification, resignation or removal of the Nominee in accordance with the terms of the Company’s By-Laws and Certification of Incorporation.

Section 4. Term and Termination.

(a) This Agreement shall become effective upon the closing of the transactions contemplated by the Purchase Agreement (the “Effective Date”).

- 3 -

(b) Notwithstanding anything to the contrary contained herein, if the Stockholder together with its Affiliates cease to Beneficially Own at least 10.0% of the Outstanding Equity, whether as a result of dilution, Transfer or otherwise, then the rights of the Stockholder under Section 2 of this Agreement shall terminate automatically (the “Nominee Termination Event”). Within three Business Days after the occurrence of the Nominee Termination Event (i) that results from a Transfer of Common Stock by the Stockholder, the Stockholder shall notify the Company of such event and (ii) that results from any other event or occurrence, the Company shall notify the Stockholder of such event (in each case, a “Nominee Termination Notice”).

(c) Notwithstanding anything to the contrary contained herein, upon the occurrence of a General Termination Event, this Agreement shall be automatically terminated and of no further force and effect, and no party hereto shall have any surviving obligations, rights, or duties hereunder after such termination. Within three Business Days after the occurrence of a General Termination Event (i) that results from a Transfer of Common Stock by the Stockholder, the Stockholder shall notify the Company of such event and (ii) that results from any other event or occurrence, the Company shall notify the Stockholder of such event (in each case, a “General Termination Notice”).

Section 5. Definitions.

“Affiliate” means, with respect to any Person, any other Person that directly, or indirectly through one or more intermediaries, controls, is controlled by, or is under common control with, such first Person.

“Agreement” has the meaning set forth in the preamble.

“Beneficially Own” has the meaning ascribed to it in Rule 13d-3 and 13d-5 (or successor rules then in effect) promulgated under Exchange Act.

“Board” means the board of directors of the Company.

“Board Observer” has the meaning set forth in Section 1.

“Business Day” means any day that is not a Saturday, Sunday, legal holiday or other day on which commercial banks in New York, New York are authorized or required by applicable law to close.

“By-Laws” means the Company’s By-Laws, as in effect on the date hereof, as the same may be amended from time to time.

“Certificate of Incorporation” means the Company’s Certificate of Incorporation, as in effect on the date hereof, as the same may be amended from time to time.

“Common Stock” means the common stock, par value $0.001 per share, of the Company.

“Company” has the meaning set forth in the preamble.

“Designation Period” means the period commencing on the Effective Date and expiring on the first to occur of a Nominee Termination Event or the third anniversary of the Effective Date.

“Director” means a duly elected member of the Board.

“Exchange Act” means the Securities Exchange Act of 1934, as amended.

- 4 -

“Expiration Time” means the earlier of (i) termination of this Agreement at the election of the Stockholder by written notice to the Company and (ii) at 5:00 p.m. (New York time) on the date that is the 180^th day following the Effective Date.

“General Termination Event” means the first to occur of (i) the Expiration Time, in the event the Stockholder declines to exercise its rights under Section 1 or Section 2 of this Agreement; (ii) the date on which the Stockholder, together with its Affiliates, ceases to Beneficially Own at least 5.0% of the Outstanding Equity, whether as a result of dilution, Transfer or otherwise; or (iii) the expiration of any time period within which Stockholder may designate a Board Observer or Nominee in accordance with Section 1 or Section 2 of this Agreement.

“Independent Director” means a Director that is an “independent director” as such term is defined from time to time in the Nasdaq Stock Market’s listing standards (or the principal national securities exchange on which Common Stock is then traded) and is not an “affiliate” or an “associate” (as such terms are defined in Rule 12b-2 of the Exchange Act) or any member of the “immediate family” (as such term is defined in Rule 16a-1 of the Exchange Act) of a director or executive officer of the Company or the Stockholder and shall not have (or have had during the past three years) any employment arrangement or other material commercial arrangement with any such person. For the avoidance of doubt, ownership of a 5% or less limited partnership interest in any fund managed by the Stockholder shall not be considered to constitute a material commercial arrangement.

“Nominee” has the meaning set forth in Section 2(a).

“Observation Election” has the meaning set forth in Section 1.

“Outstanding Equity” means, at any time, the issued and outstanding Common Stock of the Company (assuming (i) the conversion of all outstanding shares of Preferred Stock and (ii) exercise of all common stock purchase warrants then held by the Stockholder).

“Person” means an individual, a partnership, a corporation, a limited liability company, an association, a joint stock company, a trust, a joint venture, an unincorporated organization and a governmental entity or any department, agency or political subdivision thereof.

“Preferred Stock” means the Company’s Series C 15% C Convertible Redeemable Preferred Stock, par value $0.01 per share, of the Company.

“Securities Act” means the Securities Act of 1933, as amended from time to time.

“Securities Laws” means the Securities Act and the Exchange Act, and the rules promulgated thereunder.

“Stockholder” has the meaning set forth in the preamble.

“Nominee Termination Event” has the meaning set forth in Section 4.

“Nominee Termination Notice” has the meaning set forth in Section 4.

“Transfer” means any sale, transfer, assignment or other disposition of (whether with or without consideration and whether voluntary or involuntary or by operation of law) of Common Stock and/or Preferred Stock.

- 5 -

Section 6. No Assignment; Benefit of Parties; No Transfer. No party may assign this Agreement or any of its rights or obligations hereunder and any assignment hereof will be null and void. This Agreement shall be binding upon and shall inure to the benefit of the parties hereto and their respective successors and assigns for the uses and purposes set forth and referred to herein. Except as explicitly set forth herein, nothing contained in this Agreement shall confer or is intended to confer on any third party or entity that is not a party to this Agreement any rights under this Agreement.

Section 7. Remedies. The Company and the Stockholder shall be entitled to enforce their rights under this Agreement specifically, to recover damages by reason of any breach of any provision of this Agreement and to exercise all other rights existing in their favor. The parties hereto agree and acknowledge that a breach of this Agreement would cause irreparable harm and money damages would not be an adequate remedy for any such breach and that, in addition to other rights and remedies hereunder, the Company and the Stockholder shall be entitled to seek specific performance and/or injunctive or other equitable relief (without posting a bond or other security) from any court of law or equity of competent jurisdiction in order to enforce or prevent any violation of the provisions of this Agreement.

Section 8. Notices. Any notice provided for in this Agreement shall be in writing and shall be either personally delivered, or mailed first class mail (postage prepaid, return receipt requested) or sent by reputable overnight courier service (charges prepaid) to the Company at the addresses set forth below and to the Stockholder at the addresses set forth below. Notices shall be deemed to have been given hereunder when delivered personally, three days after deposit in the U.S. mail and one day after deposit with a reputable overnight courier service.

Section 9. Adjustments. If, and as often as, there are any changes in the Common Stock by way of stock split, stock dividend, combination or reclassification, or through merger, consolidation,

- 6 -

reorganization, recapitalization or sale, or by any other means, appropriate adjustment shall be made in the provisions of this Agreement, as may be required, so that the rights, privileges, duties and obligations hereunder shall continue as so changed.

Section 10. No Strict Construction. The language used in this Agreement shall be deemed to be the language chosen by the parties hereto to express their mutual intent, and no rule of strict construction shall be applied against any party.

Section 11. No Third-Party Beneficiaries. Nothing in this Agreement, express or implied, is intended or shall be construed to confer upon, or give to, any person or entity other than the parties hereto and their respective successors and assigns, any remedy or claim under or by reason of this Agreement or any terms, covenants or conditions hereof, and all of the terms, covenants, conditions, promises and agreements contained in this Agreement shall be for the sole and exclusive benefit of the parties hereto and their respective successors and assigns.

Section 12. Further Assurances. Each of the parties hereby agrees that it will hereafter execute and deliver any further document, agreement, instruments of assignment, transfer or conveyance as may be necessary or desirable to effectuate the purposes hereof.

Section 13. Counterparts. This Agreement may be executed in one or more counterparts, and may be delivered by means of facsimile or electronic transmission in portable document format, each of which shall be deemed to be an original and shall be binding upon the party who executed the same, but all of such counterparts shall constitute the same agreement.

Section 14. Governing Law. All issues and questions concerning the construction, validity, interpretation and enforceability of this Agreement shall be governed by, and construed in accordance with, the laws of the State of Delaware, without giving effect to any choice of law or conflict of law rules or provisions (whether of the State of Delaware or any other jurisdiction) that would cause the application of the laws of any jurisdiction other than the State of Delaware.

Section 15. Mutual Waiver of Jury Trial. The parties hereto hereby irrevocably waive any and all rights to trial by jury in any legal proceeding arising out of or related to this Agreement. Any action or proceeding whatsoever between the parties hereto relating to this Agreement shall be tried in a court of competent jurisdiction by a judge sitting without a jury.

Section 16. Complete Agreement; Inconsistent Agreements. This Agreement represents the complete agreement between the parties hereto as to all matters covered hereby, and supersedes any prior agreements or understandings between the parties.

Section 17. Severability. In the event any one or more of the provisions contained in this Agreement should be held invalid, illegal or unenforceable in any respect, the validity, legality and enforceability of the remaining provisions contained herein shall not in any way be affected or impaired thereby (it being understood that the invalidity of a particular provision in a particular jurisdiction shall not in and of itself affect the validity of such provision in any other jurisdiction). The parties shall endeavor in good-faith negotiations to replace the invalid, illegal or unenforceable provisions with valid provisions the economic effect of which comes as close as possible to that of the invalid, illegal or unenforceable provisions.

Section 18. Amendment and Waiver. Except as otherwise provided herein, no modification, amendment or waiver of any provision of this Agreement shall be effective against the Company or the Stockholder unless such modification is approved in writing, in the case of an amendment, by the

- 7 -

Company and the Stockholder, and in the case of a waiver, by each party against whom the waiver is to be effective. The failure of any party to enforce any of the provisions of this Agreement shall in no way be construed as a waiver of such provisions and shall not affect the right of such party thereafter to enforce each and every provision of this Agreement in accordance with its terms.

[SIGNATURE PAGE FOLLOWS]

- 8 -

IN WITNESS WHEREOF, the parties hereto have executed this Agreement on the day and year first above written.

Signature Page to Board Nomination and Observer Agreement

- 9 -