We report on the results from the observations in the very high energy band (VHE; Eγ>=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 γ-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 γ-ray signals at the 4.0 σ significance level (3.2 σ 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 σ (4.1 σ 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/(dAdtdE)=(2.3+/-0.6)×10-12(E/1 TeV)-3.2+/-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.