Haroldo Coimbra Veloso nasceu no Rio de Janeiro, então Distrito Federal, no dia 4 de julho de 1920, filho de Paulo Veloso e Diva Coimbra Veloso. Sentou praça em abril de 1939, ingressando na Escola Militar do Realengo, no Rio. Fez o curso de engenharia aérea e em abril de 1951 foi promovido a major-aviador.

Após o suicídio de Getúlio Vargas, delineou-se o quadro sucessório com a indicação, pelo Partido Social Democrático (PSD), da candidatura do então governador de Minas Gerais, Juscelino Kubitschek. Logo em seguida estabeleceu-se a aliança entre o PSD e o Partido Trabalhista Brasileiro (PTB), sendo João Goulart indicado candidato à vice-presidência. Essa aliança fez recrudescer a oposição da União Democrática Nacional (UDN) e levou alguns chefes militares a se manifestarem contra a candidatura de Goulart, acusado de esquerdista. Ao mesmo tempo, o setor mais radical da UDN pregava um golpe de Estado para impedir as eleições que, todavia, foram realizadas em outubro de 1955, dando a vitória a Juscelino Kubitschek e João Goulart.

Em 9 de novembro seguinte, com o afastamento do presidente Café Filho o governo foi assumido por Carlos Luz, que havia sido contrário à candidatura de Juscelino. No dia 11 o general Henrique Teixeira Lott liderou um movimento militar que provocou o impedimento de Carlos Luz – acusado de aderir a uma conspiração em preparo no âmbito do governo para impedir a posse dos eleitos – empossando na chefia da nação o vice-presidente do Senado, Nereu Ramos. Ficou assim garantida a posse de Juscelino e Goulart, que ocorreu em 31 de janeiro de 1956, apesar dos protestos da UDN e do descontentamento de alguns segmentos das forças armadas.

Haroldo Veloso representava um setor da Aeronáutica descontente com o regime desde a primeira derrota do brigadeiro Eduardo Gomes em 1945, e sensível às pregações udenistas. Assim, em 1956 liderou a Revolta de Jacareacanga, lugarejo situado no município de Itaituba (PA), próximo à fronteira com o Amazonas e a 300km de Manaus. O levante, de oposição à corrente militar que patrocinou o Movimento do 11 de Novembro de 1955, visava destituir o presidente e o vice-presidente recém-empossados.

Devido à sua participação neste movimento, Veloso foi preso e conduzido a Santarém, onde ficou detido a bordo do navio Getúlio Vargas. Levado para Belém, respondeu a inquérito policial-militar enquanto permanecia preso no Parque da Aeronáutica. No dia seguinte à sua prisão, 1º de março de 1956, Juscelino Kubitschek enviou ao Congresso o anteprojeto de lei que concedia anistia geral a todos os que tivessem conspirado contra o governo desde 10 de novembro de 1955.

No final do governo Kubitschek, já articulada a sucessão presidencial, Jânio Quadros apresentava-se como o único candidato capaz de derrotar a coligação entre o PSD e o PTB, que se achava no poder. Apesar de apartidário, Jânio Quadros contava com o apoio da UDN e dos setores militares descontentes com o rumo político assumido pelo governo Kubitschek, inclusive o setor da Aeronáutica que participara da Revolta de Jacareacanga.

Em 25 de novembro de 1959, a renúncia de Jânio como candidato às eleições presidenciais de 1960 e a suspeita de uma conspiração de esquerda que seria liderada por Leonel Brizola geraram outra crise militar — a Revolta de Aragarças. Haroldo Veloso participou também desse movimento liderado por João Paulo Burnier.

Após o movimento político-militar de 31 de março de 1964, que destituiu o presidente João Goulart, Veloso requereu sua entrada para a reserva remunerada como brigadeiro. Com a edição do Ato Institucional nº 2 em 1965 e a posterior instauração do bipartidarismo, Veloso filiou-se à Aliança Renovadora Nacional (Arena), de orientação governista. No pleito de novembro de 1966, elegeu-se deputado federal pelo Pará na legenda da Arena. Ocupou uma cadeira na Câmara em fevereiro de 1967.

Ao longo de seu mandato, denunciou a existência de aeroportos clandestinos na Amazônia, que serviam a empresas estrangeiras. Foi casado com Maria de Lurdes Leal Veloso. Faleceu no Rio de Janeiro em 22 de outubro de 1969.