We report on the results from the observations in the very high energy band (VHE; unk greater than or equal to 100 GeV) of the black hole X-ray binary (BHXB) Cygnus X-1. The observations were performed with the MAGIC telescope, for a total of 40 hr during 26 nights, spanning the period between 2006 June and November. Searches for steady Y-ray signals yielded no positive result, and upper limits to the integral flux ranging between 1% and 2% of the Crab Nebula flux, depending on the energy, have been established. We also analyzed each observation night independently, obtaining evidence of Y-ray signals at the 4.0 sigma significance level (3.2 sigma after trial correction) for 154 minutes of effective on-time (EOT) on September 24 between 20:58 and 23:41 UTC, coinciding with an X-ray flare seen by RXTE, Swift, and INTEGRAL. A search for faster-varying signals within a night resulted in an excess with a significance of 4.9 sigma (4.1 sigma after trial correction) for 79 minutes EOT between 22:17 and 23:41 UTC. The measured excess is compatible with a pointlike source at the position of Cygnus X-1 and excludes the nearby radio nebula powered by its relativistic jet. The differential energy spectrum is well fitted by an unbroken power law described as dN/(dA dt dE) = (2.3 plus or minus 0.6) x 10- super(12)(E/1TeV) super(-3.2 plus or minus 0.6). This is the first experimental evidence of VHE emission from a stellar mass black hole and therefore from a confirmed accreting X-ray binary.