We present the first catalog of 67 strong galaxy-galaxy lens candidates discovered in the 1.64 deg(2) Hubble Space Telescope COSMOS survey. Twenty of these systems display multiple images or strongly curved large arcs. Our initial search is performed by visual inspection of the data and is restricted, for practical considerations, to massive early-type lens galaxies with arcs found at radii smaller than similar to 5 ''. Simple mass models are constructed for the best lens candidates, and our results are compared to the strong lensing catalogs of the SLACS survey and the CASTLES database. These new strong galaxy-galaxy lensing systems constitute a valuable sample to study the mass distribution of early-type galaxies and their associated dark matter halos. We further expect this sample to play an important role in the testing of software algorithms designed to automatically search for strong gravitational lenses. From our analysis a robust lower limit is derived for the expected occurrence of strong galaxy-galaxy systems in current and future space-based wide-field imaging surveys. We expect that such surveys should uncover a large number of strong lensing systems (more than 10 systems per square degree), which will allow for a detailed statistical analysis of galaxy properties and will likely lead to constraints on models of gravitational structure formation and cosmology.