We report the results of a survey of the Small Magellanic Cloud (SMC) for radio pulsars conducted with the 20-cm multibeam receiver of the Parkes 64-meter telescope. This survey targeted a more complete region of the SMC than a previous pulsar search and had an improvement in sensitivity by a factor of about two for most pulsar periods. This survey is much more sensitive to fast young pulsars (with P < 100 ms) and is the first survey of the SMC with any sensitivity to millisecond pulsars. Two new pulsars were discovered in the survey, one of which is located within the SMC. The number of pulsars found in the survey is consistent with the expected number derived using several methods. We also report the serendipitous discovery of a new pulsar in the 30 Doradus region of the Large Magellanic Cloud (LMC). These discoveries bring the total number of rotation-powered pulsars currently known in the Magellanic Clouds to eight. We have also made refined timing measurements for the new discoveries as well as for three previously known LMC pulsars. The age distribution of luminous Magellanic Cloud pulsars supports the conjecture that pulsars younger than about 5 Myr are more luminous on average than older pulsars.

14 pages, including 6 figures and 3 tables. Accepted for publication in ApJ