Paulino Cícero de Vasconcelos nasceu em São Domingos da Prata (MG) no dia 12 de janeiro de 1937. Bacharelou-se em Ciências Jurídicas e Sociais pela Faculdade de Direito da Universidade de Minas Gerais, atual Universidade Federal de Minas Gerais (UFMG), em 1959, exercendo a advocacia em sua cidade natal.

Filiado ao Partido Social Democrático (PSD), foi prefeito de São Domingos da Prata (1959-1963). Transferiu-se depois para o Partido Social Progressista (PSP), pelo qual elegeu-se deputado estadual para a legislatura 1963-1967. Reeleito em 1966 - desta feita na legenda da Aliança Renovadora Nacional (Arena) -, no ano seguinte fez o curso da Associação dos Diplomados da Escola Superior de Guerra (Adesg).

Elegeu-se deputado federal pela legenda arenista nos pleitos de 1970, 1974 e 1978, tendo sido membro e presidente da Comissão de Minas e Energia da Câmara dos Deputados. Licenciado do mandato, foi secretário de Educação do Estado de Minas Gerais (1979-1981) no governo Francelino Pereira do Santos (1979-1983). Entre 1983 e 1987, então filiado ao Partido Democrático Social (PDS), exerceu mais um mandato de deputado federal. Durante a legislatura, transferiu-se para o Partido da Frente Liberal (PFL).

Foi presidente da Associação Brasileira para o Desenvolvimento das Atividades Técnicas e Científicas na Área Nuclear, entre 1987 e 1990, e da Usinas Siderúrgicas de Minas Gerais (Usiminas), em 1988. Eleito pelo Partido da Social Democracia Brasileira (PSDB), voltou a ocupar uma cadeira na Câmara federal na legislatura 1991-1995, licenciando-se do mandato, entre 1992 e 1993, para chefiar o Ministério das Minas e Energia (MME) no governo Itamar Franco (1992-1994), em substituição a Marcus Vinícius Pratini de Moraes.

Assumiu a pasta em outubro de 1992. Durante a sua gestão foram implementadas medidas com vistas ao desenvolvimento do processo de privatização das empresas de energia elétrica estatais, destacando-se a mudança legislativa consignada na Lei n.° 8.361, de 1993, a qual estabeleceu novo regime tarifário para as empresas de energia elétrica e com a qual se procurou criar condições para a recuperação financeira das concessionárias, tornando-as mais atrativas para os investimentos privados. Deixou a pasta em dezembro de 1993, tendo sido substituído, em caráter interino, por José Israel Vargas.

Em 1994, retornou ao PFL. Foi secretário de Administração (1997-1998) de Belo Horizonte (MG), durante a gestão do prefeito Célio de Castro (1997-2000), secretário das Minas e Energia do Estado de Minas Gerais de 1° de janeiro de 1999 a 11 de agosto de 2000 e tomou posse como secretário de Agricultura deste estado em 6 de dezembro de 2001, na administração de Itamar Franco (1998 -2002) no governo estadual.

Publicou Nossa política do estanho (1971), Plano siderúrgico nacional (1972), Nossa política de Minas e Energia (1973), A fecunda convivência dos povos (1975), Acordo nuclear Brasil-Alemanha (1976), Relatório sobre gás liqüefeito de petróleo (1976), Aleijadinho, patrono da arte no Brasil (1977) e Estudo sobre o negro no Brasil, pós-abolição (1985).