We explored the regions within a radius of 25 arcsec around 473 nearby, low-metallicity G- to M-type stars using (VR)I optical filters and small-aperture telescopes. About 10% of the sample was searched up to angular separations of 90 arcsec. We applied photometric and astrometric techniques to detect true physical companions to the targets. The great majority of the sample stars was drawn from the Carney-Latham surveys; their metallicities range from roughly solar to [Fe/H] = -3.5 dex. Our I-band photometric survey detected objects that are between 0 and 5 mag fainter (completeness) than the target stars; the maximum dynamical range of our exploration is 9 mag. We also investigated the literature, and inspected images from the Digitized Sky Surveys to complete our search. By combining photometric and proper motion measurements, we retrieved 29 previously known companions, and identified 13 new proper motion companions. Near-infrared 2MASS photometry is provided for the great majority of them. Low-resolution optical spectroscopy (386-1000 nm) was obtained for eight of the new companion stars. These spectroscopic data confirm them as cool, late-type, metal-depleted dwarfs, with spectral classes from esdK7 to sdM3. After comparison with low-metallicity evolutionary models, we estimate the masses of the proper motion companion stars to be in the range 0.5-0.1 M&sun;. They are moving around their primary stars at projected separations between ˜32 and ˜57 000 AU. These orbital sizes are very similar to those of solar-metallicity stars of the same spectral types. Our results indicate that about 15% of the metal-poor stars have stellar companions in wide orbits, which is in agreement with the binary fraction observed among main sequence G- to M-type stars and T Tauri stars. Based on observations made with the IAC80 telescope operated on the island of Tenerife by the Instituto de Astrofísica de Canarias in the Spanish Observatorio del Teide; also based on observations made with the 2.2 m telescope of the German-Spanish Calar Alto Observatory (Almería, Spain), the William Herschel Telescope (WHT) operated on the island of La Palma by the Isaac Newton Group in the Spanish Observatorio del Roque de los Muchachos (ORM) of the Instituto de Astrofísica de Canarias; and the Telescopio Nazionale Galileo (TNG) at the ORM. The complete Table 1 is only available in electronic form at the CDS via anonymous ftp to cdsarc.u-strasbg.fr (130.79.128.5) or via http://cdsweb.u-strasbg.fr/cgi-bin/qcat?J/A+A/419/167