We have undertaken a long-term project, DIRECT, to obtain the direct distances to two important galaxies in the cosmological distance ladder, M31 and M33, using detached eclipsing binaries (DEBs) and Cepheids. While rare and difficult to detect, DEBs provide us with the potential to determine these distances with an accuracy better than 5%. The extensive photometry obtained in order to detect DEBs provides us with good light curves for the Cepheid variables. These are essential to the parallel project to derive direct Baade-Wesselink distances to Cepheids in M31 and M33. For both Cepheids and eclipsing binaries, the distance estimates will be free of any intermediate steps. As a first step in the DIRECT project, between 1996 September and 1997 January we obtained 36 full nights on the Michigan-Dartmouth-MIT Observatory 1.3m telescope and 45 full/partial nights on the F. L. Whipple Observatory 1.2m telescope to search for DEBs and new Cepheids in the M31 and M33 galaxies. In this paper, second in a series, we present the catalog of variable stars, most of them newly detected, found in the field M31A [({alpha},{delta})=(11.34{deg}, 41.73{deg}), J2000.0]. We have found 75 variable stars: 15 eclipsing binaries, 43 Cepheids, and 17 other periodic, possible long-period or nonperiodic variables. The catalog of variables, as well as their photometry and finding charts, is available via anonymous ftp and the World Wide Web. The CCD frames are available upon request.