<PAGE>
 
                                  UNITED STATES
                       SECURITIES AND EXCHANGE COMMISSION
                             Washington, D.C. 20549

    
                                 FORM 10-K/A      


[X]    Annual Report Pursuant to Section 13 or 15(d) of the Securities 
       Exchange Act of 1934 for the fiscal year ended December 31, 1996

[_]    Transition Report Pursuant to Section 13 or 15(d) of the Securities
       Exchange Act of 1934 for the transition period from _____ to _____

                         Commission File Number: 0-27468

                              ULTRADATA CORPORATION
             (Exact name of registrant as specified in its charter)

           Delaware                                      94-2746681
   (State or other jurisdiction                       (I.R.S. Employer
 of incorporation or organization)                   Identification No.)

 5000 Franklin Drive, Pleasanton, CA                     94588-3031
 (Address of principal executive officer)                (Zip Code)

               Registrant's telephone number, including area code:
                                  510/463-8356

Indicate by check mark whether the registrant (1) has filed all reports required
to be filed by Section 13 or 15(d) of the Securities Exchange Act of 1934 during
the preceding 12 months (or for such shorter period that the registrant was
required to file such reports), and (2) has been subject to such filing
requirements for the past 90 days.
                            Yes [X]      No [_]

Indicate by check mark if disclosure of delinquent filers pursuant to Item 405
of Regulation S-K is not contained herein, and will not be contained, to the
best of registrant's knowledge, in definitive proxy or information statements
incorporated by reference in Part III of this Form 10-K or any amendment to this
Form 10-K. _____

The aggregate market value of the voting stock held by non-affiliates of the
registrant as of March 20, 1997, was approximately $11,134,196 (based on the
last reported sale price of $4.00 per share on March 20, 1997 on the Nasdaq
National Market).

As of March 20, 1997, Registrant had outstanding 7,575,291 shares of Common
Stock, $.001 par value.

<PAGE>
 
ITEM 11.   EXECUTIVE COMPENSATION

     The following table sets forth all compensation awarded, earned or paid for
services rendered in all capacities to the Company and its subsidiaries during
each of 1995 and 1996 to the Company's Chief Executive Officer, the Company's
four other most highly compensated executive officers who were serving as
executive officers at the end of 1996, and two highly compensated executive
officers who were not serving as executive officers at the end of 1996
(together, the "Named Executive Officers"). This information includes the dollar
values of base salaries, bonus awards, the number of shares subject to stock
options granted and certain other compensation, if any, whether paid or
deferred. The Company does not grant stock appreciation rights and has no
long-term compensation benefits other than the stock options.

                           SUMMARY COMPENSATION TABLE
<TABLE>
<CAPTION>
                                                                                            LONG-TERM
                                                                                          COMPENSATION
                                                            ANNUAL COMPENSATION              AWARDS
                                                 --------------------------------------   ------------
                                                                                           SECURITIES
                                      FISCAL                             OTHER ANNUAL      UNDERLYING
NAME AND PRINCIPAL POSITION            YEAR       SALARY        BONUS   COMPENSATION(1)      OPTIONS
---------------------------            ----       ------        -----   ---------------   ------------
<S>                                   <C>        <C>           <C>      <C>               <C>
Nigel P. Gallop ....................   1996      $338,381      $   --        $   --          35,000
Chief Executive Officer                1995      $530,286          --            --         600,000

Robert J. Majteles .................   1996      $ 51,250(2)   $   --        $ 14,288(3)    600,000
President and Chief Operating
Officer

Philip D. Ranger ...................   1996      $113,333      $   --        $   --           4,000
Chief Financial Officer                1995(4)   $  7,153          --            --            --

David J. Robbins ...................   1996      $110,000      $   --        $   --          20,000
Vice President, Customer Services      1995(6)   $  9,871          --            --            --

James R. Graham, II ................   1996      $251,515          --        $ 40,565(7)     50,000
Former President and Chief Operating   1995      $210,484          --        $  8,198          --
Officer

Whitelaw Wright III ................   1996      $191,050      $ 27,000(5)   $   --          20,000
Former Executive Vice President,       1995      $153,713          --        $  6,260          --
Product Development

Mary K. Pecka ......................   1996      $164,931      $   --        $ 16,584(7)       --
Former Executive Vice President,       1995      $153,713          --        $  6,687          --
Training and Installation
</TABLE>
---------------

(1)  Unless otherwise noted, consists of contributions made by the Company to
     each Named Executive Officer's 401(k) plan account in 1995. These
     contributions are subject to a vesting schedule that provides for vesting
     of 20% of the contributions for each year of service with the Company.

(2)  Mr. Majteles commenced employment with the Company in October 1996. Mr.
     Majteles was appointed Chief Executive Officer in April 1997.

(3)  Represents payment to Mr. Majteles for relocation expenses.

(4)  Mr. Ranger was employed by the Company as its Director of Finance in
     December 1995.

(5)  The Company paid Mr. Wright a discretionary $27,000 bonus reflecting
     performance in 1995 and determined in 1996.

(6)  Mr. Robbins commenced employment as Vice-President, Customer Services in
     December 1995.

(7)  Represents accrued vacation paid upon termination of employment.

     The following table sets forth further information regarding option grants
during 1996 to each of the Named Executive Officers. Except with respect to the
option granted to Mr. Majteles, all options were granted pursuant to the
Company's 1994 Equity Incentive Plan. In accordance with the rules of the
Securities and Exchange Commission, the table sets forth the hypothetical gains
or "option spreads" that would exist for the options at the end of their
respective ten-year terms. These gains are based on assumed rates of annual
compound stock price appreciation of 5% and 10% from the date the option was
granted to the end of the option term.
<PAGE>
 
                              OPTION GRANTS IN 1996
<TABLE>    
<CAPTION>

                                                                                  POTENTIAL REALIZABLE      
                         NUMBER OF    PERCENTAGE OF                              VALUE AT ASSUMED ANNUAL    
                        SECURITIES    TOTAL OPTIONS  EXERCISE                      RATES OF STOCK PRICE     
                        UNDERLYING      GRANTED TO    PRICE                  APPRECIATION FOR OPTION TERM(2) 
                         OPTIONS      EMPLOYEES IN     PER      EXPIRATION   -------------------------------
         NAME           GRANTED(1)        1996        SHARE        DATE           5%                10%
---------------------   ----------    -------------  --------   ----------   -------------     -------------
<S>                     <C>           <C>            <C>        <C>          <C>               <C>

Nigel P. Gallop ......    35,000             3.8%      $6.625     8/23/06    $  145,824.94     $  369,548.46 
                                                                                                              
Robert J. Majteles ...   600,000            65.3%      $3.50     10/17/06    $1,320,676.66     $3,346,854.00 
                                                                                                              
Philip D. Ranger .....     4,000             0.4%      $7.25       2/8/06    $   18,237.94     $   46,218.53 
                                                                                                              
David J. Robbins .....    20,000             2.2%      $7.25       2/8/06    $   91,189.72     $  231,092.30 
                                                                                                              
James R. Graham, II ..    50,000             5.4%      $6.625     6/29/97    $  208,321.34     $  527,926.38 

Whitelaw Wright III ..    20,000             2.2%      $7.25       2/8/06    $   91,189.72     $  231,092.30 
                                                                                                              
Mary K. Pecka ........      --                --        --           --               --                --        
</TABLE>     
-------------
(1)  The options shown in the table were granted at fair market value, are (with
     the exception of the nonqualified option grant to Mr. Majteles) incentive
     stock options and will expire ten years from the date of grant, subject to
     earlier termination upon termination of the optionee's employment. The
     options become exercisable over a four-year period, with 25% of the shares
     vesting on the first anniversary of the date of grant and thereafter 2.083%
     of the shares vesting for each full month that the optionee renders
     services to the Company.

(2)  The 5% and 10% assumed annual compound rates of stock price appreciation
     are mandated by the rules of the Securities and Exchange Commission and do
     not represent the Company's estimate or projection of future Common Stock
     prices.

     The following table sets forth certain information concerning the exercise
of options by each of the Named Executive Officers during 1996, including the
aggregate amount of gains on the date of exercise. In addition, the table
includes the number of shares covered by both exercisable and unexercisable
stock options as of December 31, 1996. Also reported are values of
"in-the-money" options that represent the positive spread between the respective
exercise prices of outstanding stock options and $4.125 per share, which was the
closing price of the Company's Common Stock as reported on the Nasdaq National
Market on December 31, 1996, the last day of trading for 1996.

             AGGREGATED OPTION EXERCISES IN 1996 AND YEAR-END VALUES

<TABLE>    
<CAPTION>

                                                           NUMBER OF SECURITIES         VALUE OF UNEXERCISED
                                                          UNDERLYING UNEXERCISED       IN-THE-MONEY OPTIONS AT
                                                        OPTIONS AT FISCAL YEAR-END(1)    FISCAL YEAR-END (2)
                                                        -----------------------------  -----------------------
                              SHARES
                            ACQUIRED ON      VALUE                   
           NAME             EXERCISE(1)   REALIZED(1)  EXERCISABLE   UNEXERCISABLE     EXERCISABLE   UNEXERCISABLE
 -------------------------  -----------   -----------  -----------   -------------     -----------   -------------
<S>                         <C>           <C>          <C>           <C>               <C>           <C>

Nigel P. Gallop ..........       --              --      485,000         150,000              --           --   
                                                                                                               
Robert J. Majteles .......       --              --         --           600,000              --       $375,000
                                                                                                               
Philip D. Ranger .........       --              --         --             4,000              --           --  
                                                                                                               
David J. Robbins .........       --              --         --            20,000              --           --  
                                                                                                               
James R. Graham, II.......       --              --         --              --                --           --  
                                                                                                               
Whitelaw Wright III.......       --              --       37,500          32,500              --           --  
                                                                                                               
Mary K. Pecka ............     50,000        $30,625        --              --                --           --  
</TABLE>     

-----------

(1)  "Value Realized" represents the fair market value of the shares of Common
     Stock underlying the option on the date of exercise less the aggregate
     exercise price of the option.
<PAGE>
 
(2)  These values, unlike the amounts set forth in the column entitled "Value
     Realized," have not been, and may never be, realized and are based on the
     positive spread between the respective exercise prices of outstanding
     options and the closing price of the Company's Common Stock on December 31,
     1996, the last day of trading for 1996.


           COMPENSATION COMMITTEE INTERLOCKS AND INSIDER PARTICIPATION


     The Compensation Committee consists of Messrs. Howell and Stuckey. For
a description of transactions between the Company and members of the
Compensation Committee and entities affiliated with such members, see the
discussion under "Certain Relationships and Related Transactions" below.


                              EMPLOYMENT AGREEMENTS

        
     The Company is a party to an employment agreement dated as of January 1,
1992 with Nigel P. Gallop (the "Former Employment Agreement") pursuant to which
he served as President and Chief Executive Officer of the Company. Under the
Former Employment Agreement, Mr. Gallop's base salary was initially set at
$443,000 per year, which was increased annually to adjust for inflation. In
addition, Mr. Gallop was entitled to receive an incentive bonus equal to 30% of
the amount by which royalties paid to the Company's stockholders and the
Company's profits exceeded 12% of the Company's gross revenues. Mr. Gallop was
also entitled to certain medical and disability benefits, reimbursement of
various expenses, including expenses associated with his relocation from
Australia to the United States, the use of an automobile and certain other
benefits. The Former Employment Agreement expired on December 31, 1996 and
provided for the continued payment of Mr. Gallop's base salary, benefits and
reimbursement of expenses through December 31, 1996 in the event that he was
terminated other than for cause. In July 1995, the Company approved a new
Employment Agreement with Mr. Gallop (the "Current Employment Agreement")
pursuant to which he was to continue to serve as the Company's President and
Chief Executive Officer. The Current Employment Agreement superseded the Former
Employment Agreement effective March 1, 1996. Under the current Employment
Agreement, he received a base salary at the rate of $300,000 per year from March
1, 1996 through December 31, 1996, which was to be increased annually to account
for inflation, and he was entitled to benefits similar to those under the Former
Employment Agreement. The Current Employment Agreement will expire on December
31, 1998, unless terminated earlier in accordance with its provisions. If Mr.
Gallop's employment is terminated by the Company other than for cause, the
Current Employment Agreement provides that he will receive as severance his base
salary, benefits and reimbursement of expenses through December 31, 1998. In
October 1996 and April 1997, Mr. Gallop ceased being President and Chief
Executive Officer, respectively, although he continues to be Chairman of the
Company.     

        
     The Company is currently negotiating a severance package with Mr. Gallop
that is expected to include: (a) termination of the Current Employment
Agreement; (b) cash severance of approximately $260,000; (c) transfer of
property valued at approximately $70,000; (d) acceleration of exercisability of
options to purchase 150,000 shares of Common Stock with an exercise price of
$6.00 per share; (e) extension of exercisability of options to purchase 600,000
shares of Common Stock with an exercise price of $6.00 per share (including
the accelerated shares) through expiration in July 2000; (f) reimbursement of
relocation expenses as incurred up to $100,000 and (g) an agreement by Mr.
Gallop not to receive any additional compensation as a director of the
Company, including but not limited to options under the Directors Plan, other
than reimbursement of expenses incurred on behalf of the Company.     

     The Company also is a party to an employment agreement effective as of
October 17, 1996 with Robert J. Majteles pursuant to which he served as the
Company's President and Chief Operating Officer, which provides for Mr. Majteles
to receive an annual salary of $250,000. Mr. Majteles also is entitled to
certain medical and disability benefits and reimbursement of expenses associated
with his relocation to California. Mr. Majteles is eligible to receive a bonus
of up to 30% of his base salary annually according to a bonus plan approved by
the Compensation Committee. The Company also granted to Mr. Majteles
nonqualified options outside of the Incentive Plan to purchase 600,000 shares of
common stock at $3.50 per share. These options vest over four years, with 25% of
the shares becoming exerciseable on October 17, 1997 and the remaining shares
vesting in equal increments monthly throughout the remainder of the period. In
addition, such options automatically accelerate immediately prior to the 
<PAGE>
 
closing of (a) a merger or acquisition in which the Company is not the surviving
entity (with certain exceptions); (b) a sale, transfer or other disposition of
all or substantially all of the assets of the Company; (c) or any other
corporate reorganization or business combination in which the beneficial
ownership of 50% of more of the Company's outstanding voting stock is
transferred. In addition, beginning January 1, 1998 and annually throughout
employment, Mr. Majteles is entitled to receive an ongoing option grant, subject
to board approval. The number of shares subject to such option grant will be
equal to $150,000 divided by the fair market value per share on the date of
grant and will be granted at fair market value. If Mr. Majteles is terminated by
the Company other than for cause, the Company will provide Mr. Majteles with a
severance payment equivalent to Mr. Majteles' then-current base salary plus 30%
of such base salary. Mr. Majteles was appointed Chief Executive Officer of the
Company in April 1997.

                             DIRECTOR COMPENSATION

        
     The Company reimburses the members of its Board of Directors for reasonable
expenses associated with their attendance at Board meetings. Non-employee
directors are entitled to receive a quarterly retainer fee of $1,500, plus
$1,000 per Board meeting and $500 per committee meeting. Members of the Board
who are not employees of the Company, or any parent, subsidiary or affiliate of
the Company, are eligible to participate in the Company's 1995 Directors Stock
Option Plan. For a discussion of the provisions of the 1995 Directors Stock
Option Plan, see "Summary of 1995 Directors Stock Option Plan." In 1996, the
Company granted no options to directors under the 1995 Directors Stock Option
Plan.     

    
ITEM 12.  SECURITY OWNERSHIP OF CERTAIN BENEFICIAL OWNERS AND MANAGEMENT     

  The following table sets forth certain information, as of April 15, 1997,
with respect to the beneficial ownership of the Company's Common Stock by: (i)
each stockholder known by the Company to be the beneficial owner of more than
5% of the Company's Common Stock; (ii) each director and nominee; (iii) each
Named Executive Officer; and (iv) all directors and executive officers as a
group.
 
<TABLE>    
<CAPTION>
 NAME AND ADDRESS OF BENEFICIAL    AMOUNT AND NATURE OF   PERCENT OF OUTSTANDING
              OWNER               BENEFICIAL OWNERSHIP(1)    COMMON STOCK(1)
 ------------------------------   ----------------------- ----------------------
 <S>                              <C>                     <C>
 Nigel P. Gallop(2).............         1,729,000                 21.5%
  c/o ULTRADATA Corporation
  5000 Franklin Drive
  Pleasanton, California 94588-
  3544
 Andrew J. Phelan...............         1,279,000                 16.9%
  c/o Ultradata Australia
  25 Richardson Street
  West Perth 6005
  Australia
 Brian N. Dean..................         1,178,742                 15.6%
  1919 Malvern Road
  East Malvern Victoria
  Australia 3145
 Malcolm R. McKellar............         1,055,000                 13.9%
  25 Endeavor Street
  Port Douglas 4871
  Australia
 John F. Carlson................                --                   --%
 Lawrence M. Howell(3)..........            21,300                    *
 M. M. Stuckey(4)...............             7,500                    *
 Robert J. Majteles.............                --                   --%
 Philip D. Ranger(5)............             1,499                    *
 David J. Robbins(6)............             7,499                    *
 James R. Graham, II(7).........            66,665                    *
 Whitelaw Wright III(8).........            38,541                    *
 Mary K. Pecka..................                --                   --%
 All executive officers and
  directors as a group
  (10 persons)(9)...............         1,872,004                 23.0%
</TABLE>     
--------
 *  Less than 1%
(1) Unless otherwise indicated below, the persons and entities named in the
    table have sole voting and sole investment power with respect to all
    shares beneficially owned, subject to community property laws where
    applicable. Shares of Common Stock subject to options that are currently
    exercisable or exercisable within 60 days of April 15, 1997 are deemed to
    be outstanding and to be beneficially owned by the person holding such
    options for the purpose of computing the percentage ownership of such
    person but are not treated as outstanding for the purpose of computing the
    percentage ownership of any other person.
(2) Includes 450,000 shares of Common Stock subject to options exercisable
    within 60 days of April 15, 1997. Mr. Gallop is a director of the Company.
(3) Includes 11,400 shares held by the Howell Revocable Trust and 4,900 shares
    held by the Howell Children's Trust. Also includes 5,000 shares of Common
    Stock subject to options exercisable within 60 days of April 15, 1997. Mr.
    Howell is a director of the Company.
(4) Includes 5,000 shares of Common Stock subject to options exercisable
    within 60 days of April 15, 1997. Mr. Stuckey is a director of the
    Company.
(5) Includes 1,499 shares of Common Stock subject to options exercisable
    within 60 days of April 15, 1997. Mr. Ranger is Chief Financial Officer of
    the Company.
    
(6) Includes 7,499 shares of Common Stock subject to options exercisable within
    60 days of April 15, 1997. Mr. Robbins is Vice President,Customer Services 
    of the Company.     
             
(7) Includes 66,665 shares of Common Stock subject to options exercisable
    within 60 days of April 15, 1997. Mr. Graham is a former President and
    Chief Operating Officer of the Company.     
    
(8) Includes 38,541 shares of Common Stock subject to options exercisable
    within 60 days of April 15, 1997. Mr. Wright is a former Executive Vice
    President, Product Development of the Company.     
    
(9) Includes 574,204 shares of Common Stock subject to options exercisable
    within 60 days of April 15, 1997, including the options described in
    footnotes (2) through (8).      


ITEM 13.  CERTAIN RELATIONSHIPS AND RELATED TRANSACTIONS 

        
     From January 1, 1996 to the present, there are no currently proposed 
transactions in which the amount involved exceeds $60,000 to which the Company 
or any of its subsidiaries was (or is to be) a party and in which any executive 
officer, director, 5% beneficial owner of the Company's Common Stock or member 
of the immediate family of any of the foregoing persons had (or will have) a 
direct or indirect material interest, except for: (i) transactions set forth 
under "Executive Compensation" above; (ii) indemnification agreements entered 
into by the Company with each of its directors and executive officers that 
provide the maximum indemnity available to directors and executive officers 
under Section 145 of the Delaware General Corporation Law and the Company's 
Bylaws, as well as certain additional procedural protections; and (iii) a loan 
in the amount of $110,000 from the Company to Nigel P. Gallop, which loan was 
repaid by Mr. Gallop. Such indemnity agreements provide generally that the 
Company will advance expenses incurred by directors and executive officers in 
any action or proceeding as to which they may be indemnified, and require the 
Company to indemnify such individuals to the fullest extent permitted by law. 
    

<PAGE>
 
                                   SIGNATURES


     Pursuant to the requirements of Section 13 or 15(d) of the Securities
Exchange Act of 1934, the Registrant has duly caused this Amendment No. 1 on
Form 10-K/A to be signed on its behalf by the undersigned, thereunto duly
authorized, this 8th day of May 1997.

                              ULTRADATA Corporation


                              By: *Robert J. Majteles
                                   President, Chief Executive Officer, 
                                   and Director


     Pursuant to the requirements of the Securities Exchange Act of 1934, this
amendment to report has been signed below by the following persons on behalf of
the registrant and in the capacities and on the dates indicated below.

              Signature                         Title                Date
----------------------------------   --------------------------   -----------
PRINCIPAL EXECUTIVE OFFICER:

*Robert J. Majteles                  President, Chief Executive   May 8, 1997
                                     Officer and Director

PRINCIPAL FINANCIAL OFFICER AND
PRINCIPAL ACCOUNTING OFFICER:

/s/ Philip D. Ranger                 Chief Financial Officer      May 8, 1997
----------------------------------                      
Philip D. Ranger

ADDITIONAL DIRECTORS:

*John Carlson                        Director                     May 8, 1997

*Lawrence M. Howell                  Director                     May 8, 1997

*M.M. Stuckey                        Director                     May 8, 1997

*By:/s/ Philip D. Ranger
    ------------------------------
        Philip D. Ranger
        Attorney-in-fact