We define several types of pseudoprimes with respect to Lucas sequences and prove the analogs of various theorems about ordinary pseudoprimes. For example, we show that Lucas pseudoprimes are rare and we count the Lucas sequences modulonwith respect to whichnis a Lucas pseudoprime. We suggest some powerful new primality tests which combine Lucas pseudoprimes with ordinary pseudoprimes. Since these tests require the evaluation of the least numberf(n)f(n)for which the Jacobi symbol(f(n)/n)(f(n)/n)is less than 1, we evaluate the average order of the functionf.