Naheed Nenshi est né à Toronto et a grandi à Calgary. Il complète un baccalauréat en commerce à l’Université de Calgary, puis il obtient une maîtrise en politique publique de la John F. Kennedy School of Government de l’Université d’Harvard en 1998. Par ailleurs, son intérêt pour la langue française l’amène à faire une immersion à l’Université Laval, à Québec, au cours de l’été 1998.

M. Nenshi fait ses premières armes chez McKinsey & Co., une société de consultants en gestion dans les secteurs des télécommunications, de la finance, de la vente au détail et dans certaines compagnies pétrolières concernant le développement de stratégies corporatives.

Il quitte McKinsey en 2001 pour fonder sa propre entreprise de consultants en management, The Ascend Group, et conseille notamment des organismes à but non-lucratif ainsi que des clients corporatifs quant à leur stratégie de croissance.
Les Nations Unies, Gap et le gouvernement albertain ont compté parmi ses clients.

Entre 2001 et son élection en 2010, M. Nenshi a enseigné la finance corporative et le marketing aux universités de Calgary et de Mount Royal, où il obtient une charge d’enseignement à la Bissett School of Business en gestion des organismes à but non lucratif, le premier programme du genre au Canada.

De 2006 à 2008, M. Nenshi préside le conseil du centre EPCOR pour les arts de la scène, un organisme réunissant plusieurs compagnies évoluant dans ce secteur.

C’est en mai 2010 que M. Nenshi pose sa candidature à la mairie de Calgary en vue des élections d’octobre, qu’il remporte avec 40 % des suffrages, grâce à une utilisation proactive des médias sociaux et une campagne électorale efficace auprès des jeunes électeurs. M. Nenshi devient également le premier maire d’une grande ville canadienne à être de confession musulmane.