We have conducted a search for new stars of high proper motion (greater than or equal to 0 ".4 yr(-1)) using POSS II fields, for which an extra IIIa-F (red) plate of good quality exists, along with usable IIIa-J (blue) and IV-N (infrared) plates taken at epochs differing by a minimum of 1.5 yr. Thirty-five fields at Galactic latitudes \ b \ greater than or equal to 20 degrees were measured, covering some 1378 deg(2), or 3.3% of the sky. Searches with three plate combinations, as well as all four plates, were also made. Seven new stars were found with mu greater than or equal to 0 ".15 yr(-1), which were therefore missed in the Luyten Half Second catalog (LHS). One of these is a common proper-motion binary consisting of two subdwarf M stars; another is a cool white dwarf with probable halo kinematics. As a test of our completeness-and of our ability to test that of Luyten- 216 of 230 cataloged high proper motion stars were recovered by the software, or 94%. Reasons for incompleteness of the LHS are discussed, such as the simple fact that POSS II plates have deeper limiting magnitudes and greater overlap than did POSS I. Nonetheless, our results suggest that the LHS is closer to 90% complete than recent estimates in the literature (e.g., 60%), and we propose a reason to account for one such lower estimate, The conclusion that the LHS catalog is more complete has implications for the nature of the halo dark matter. In particular, it strengthens the constraint on the local density of halo stars, especially white dwarfs at M-V similar to + 17 to + 18.