We report the observation of vortex nucleation in a rotating optical lattice. A 87Rb Bose-Einstein condensate was loaded into a static two-dimensional lattice and the rotation frequency of the lattice was then increased from zero. We studied how vortex nucleation depended on optical lattice depth and rotation frequency. For deep lattices above the chemical potential of the condensate we observed a linear dependence of the number of vortices created with the rotation frequency,even below the thermodynamic critical frequency required for vortex nucleation. At these lattice depths the system formed an array of Josephson-coupled condensates. The effective magnetic field produced by rotation introduced characteristic relative phases between neighbouring condensates, such that vortices were observed upon ramping down the lattice depth and recombining the condensates.