Faits: A. Le 5 mai 1999, un contrat de bail à loyer a été signé entre la SI A._ et Y._. La location, qui portait sur un local à l'usage d'un dépôt exclusivement, prenait effet au 1er mai 1999 pour se terminer au 30 avril 2002 et était renouvelable, au terme de la durée initiale, d'année en année. Le loyer a été fixé à 9'600 fr. par année. Le 3 juillet 2006, X._ est devenu propriétaire de l'immeuble. Le 20 du même mois, il signifiait à Y._ un avis de résiliation pour le 31 janvier 2007; dans un courrier joint à la formule officielle, il exposait être le nouveau propriétaire de l'immeuble, vouloir y habiter et avoir besoin de disposer des dépôts loués à des fins privées et professionnelles et disait être disposé à discuter avec la locataire d'une solution consistant à ne prendre possession que d'une partie des locaux. B. Le 4 août 2006, la locataire a saisi la Commission de conciliation en matière de baux et loyers d'une requête en annulation du congé et, subsidiairement, en prolongation du bail pour une durée de six ans. Par décision du 21 février 2007, la Commission de conciliation a reconnu la validité du congé signifié à la locataire et accordé à cette dernière une prolongation de trois ans, échéant le 31 janvier 2010. Le bailleur a saisi le Tribunal des baux et loyers, en invoquant l'art. 261 CO et en faisant valoir, pour s'opposer à toute prolongation de bail, son besoin propre et urgent. La locataire a principalement soutenu que le congé était nul faute d'avoir été signifié pour l'échéance légale. Elle a en outre contesté le besoin propre allégué par le propriétaire. Par jugement du 18 juin 2008, le Tribunal des baux et loyers a constaté l'inefficacité du congé signifié le 20 juillet 2006 pour le 31 janvier 2007. Le Tribunal a considéré que le bailleur souhaitait résilier de manière anticipée le bail conformément à l'art. 261 al. 2 let. a CO, mais que la condition du besoin urgent faisait, en l'état, défaut. Les premiers juges ont ainsi arrêté que le congé était inefficace et noté qu'il ne pouvait pas être transformé en congé ordinaire. Statuant le 12 janvier 2009 sur appel du bailleur, la Chambre d'appel en matière de baux et loyers a confirmé le jugement attaqué, en niant la réalisation de la condition du besoin urgent de l'art. 261 al. 2 let. a CO et en refusant de transformer le congé anticipé inefficace en un congé ordinaire. C. Agissant par la voie du recours en matière civile, le bailleur invite le Tribunal fédéral à réformer le jugement entrepris en ce sens qu'il soit constaté que le congé du 20 juillet 2006 est valable, qu'aucune prolongation de bail ne soit accordée et qu'il soit ordonné à la locataire de quitter immédiatement le dépôt loué, libre de toute personne et de tout objet. Le bailleur conclut également à la condamnation de la locataire en tous les dépens et à son déboutement de toutes autres conclusions. La locataire conclut au rejet du recours. 