We report results from a search for strangelets (small chunks of Strange Quark Matter) in lunar soil using the Yale WNSL accelerator as a mass spectrometer. We have searched over a range in mass from A=42 to A=70 amu for nuclear charges 5, 6, 8, 9, and 11. No strangelets were found in the experiment. For strangelets with nuclear charge 8, a concentration in lunar soil higher than $10^{-16}$ is excluded at the 95% confidence level. The implied limit on the strangelet flux in cosmic rays is the most sensitive to date for the covered range and is relevant to both recent theoretical flux predictions and a strangelet candidate event found by the AMS-01 experiment.