En mayo de 1964 José Afonso fue a cantar a Grândola, un pueblo del Alentejo, invitado por la Sociedade Musical Fraternidade Operária Grandolense, una sociedad obrera con banda de música y biblioteca propia. Unos días después escribió a los socios una carta de agradecimiento con un poema de tres estrofas. De ese poema salió la canción: un pueblo moreno, la fraternidad entre sus vecinos y la idea de que allí manda la gente.

La grabó en 1971 para el disco Cantigas do Maio, en un estudio instalado en un castillo del siglo XVIII a las afueras de París, con arreglos de José Mário Branco. Branco le quitó casi todos los instrumentos y le dio la forma del cante alentejano: voces y un ruido de pasos. Enseñó a Afonso y a otros dos músicos el paso arrastrado de los jornaleros que volvían del campo, y lo grabaron como percusión. La primera vez que Afonso la cantó en público fue en Santiago de Compostela, en mayo de 1972.

La censura del Estado Novo había prohibido muchas canciones suyas. Esta no. A los censores les pareció inofensiva una canción sobre la fraternidad en un pueblo. El 29 de marzo de 1974, en el Coliseu de Lisboa, en un encuentro de canción portuguesa con más de treinta canciones vetadas y la policía en la sala, la cantó al final y la siguieron varios miles de personas.

Un mes después, los militares del Movimiento de las Fuerzas Armadas necesitaban dos señales de radio. La primera fue una balada romántica sin ningún contenido político, «E depois do adeus», que sonó a las 22:55 del 24 de abril en una emisora de Lisboa. La segunda tenía que confirmar que la operación estaba en marcha. Su primera idea fue otra canción de Afonso, «Venham mais cinco», pero esa sí estaba prohibida. Eligieron «Grândola». Sonó a las 0:20 del 25 de abril en el programa Limite de Rádio Renascença, la emisora católica, después de que el locutor leyera la primera estrofa.

El oficial que organizó las señales, Carlos de Almada Contreiras, reconoció más tarde que como decisión militar había sido mala: lo prudente habría sido una canción inocua, como la primera. Aquella noche, además, el locutor estuvo a punto de poner otro disco, y fue un técnico quien cambió la cinta a tiempo.

La canción se escribió para dar las gracias a los socios de una banda de pueblo. Desde aquella noche cuesta oírla sin pensar en otra cosa.