Hijo natural de Jesusa Blanca Nieve Iribarne, que con 19 años lo dio a luz en una casa de altos, ubicada en el barrio de Belvedere, en la avenida Carlos María Ramírez esquina Carlos de la Vega. Lo recibió una partera conocida por el apodo de Bombón, que allí vivía. Cuando Blanca Iribarne estaba en trabajo de parto fue trasladada en un carro de caballo desde el pueblo de Santiago Vázquez con la intención de llegar al hospital pediátrico Pereira Rossell, pero no llegó a tiempo y fue acogida en casa de la partera. Allí nació Zitarrosa y luego lo llevaron hasta el hospital, lugar que se considera como el sitio de su nacimiento, para inscribirlo en el registro civil que allí existe.[cita requerida] Fue anotado como Alfredo Iribarne.

A poco de nacer, en circunstancias especiales, su madre lo dio a criar al matrimonio compuesto por Carlos Durán, hombre de varios oficios, y Doraisella Carbajal, empleada en el Consejo del Niño. Pasó entonces a ser Alfredo «Pocho» Durán. Con esa pareja vivió en diversos barrios de la capital uruguaya y luego, entre 1944 y fines de 1947, se trasladó al pueblo de Santiago Vázquez, con frecuentes visitas a la campaña cerca de Trinidad, capital del departamento de Flores, de donde era oriunda su madre adoptiva. Se ha señalado que esta experiencia infantil lo marcó para siempre, dado que en su repertorio resalta la inclusión mayoritaria de ritmos y canciones de origen campesino, fundamentalmente milongas.

Regresó con su familia adoptiva por breve tiempo a Montevideo, para luego, al comienzo de su adolescencia, pasar a vivir con su madre biológica y el esposo, el argentino Alfredo Nicolás Zitarrosa, quien le dio su apellido, y su hermana recién nacida, en el Rincón de la Bolsa, hoy llamado Ciudad del Plata, en el km 29.5 de la vieja ruta a Colonia, departamento de San José. Afincado allí, cursaba el liceo en Montevideo, adonde finalmente se trasladó en su temprana juventud. Vivió primero con el matrimonio Durán y luego en la pensión de la señora Ema, sita en la calle Colonia esquina Médanos (hoy Barrios Amorín), para ocupar después la famosa buhardilla de la casa que funcionaba también como pensión y era propiedad de Blanca Iribarne, su madre, ubicada en la calle Yaguarón (hoy Aquiles Lanza) 1021, enfrente de la plaza que actualmente lleva su nombre y a la vista del Cementerio Central. Trabajó, entre otros menesteres, como vendedor de muebles, de suscripciones a una sociedad médica, de oficinista y en una imprenta. Tiempo después recordaría con especial afecto al que fuera su primer empleador, un tal Pachelo, que le fue presentado por uno de sus compañeros habituales de viaje en sus traslados diarios a Montevideo, durante la época liceal.