A fundação da UCCLA ocorreu em 28 de junho de 1985 pelas cidades de Bissau, Lisboa, Luanda, Macau, Maputo, Praia, Rio de Janeiro e São Tomé/Água Grande.[3] A criação da organização é atribuída à iniciativa de Nuno Krus Abecasis, então presidente da Câmara Municipal de Lisboa.[3][9]
O orçamento da plataforma de cooperação foi decuplicado de 2002 para 2003, tendo saltado de 250 mil para 2,5 milhões de euros.[7]
Em suas primeiras décadas a presidência da entidade era detida por Lisboa.[9] Posteriormente a uma série de alterações no estatuto, foi introduzido o princípio da rotatividade na assembleia-geral realizada em 2009 na capital portuguesa.[9] A assembleia seguinte foi em março de 2010 em Salvador, que foi a primeira a suceder Lisboa na presidência da organização, na qual o mandato dura por dois anos.[9][10]