In a cooling structure for a recovery-type air-cooled gas turbine combustor having a recovery-type air-cooling structure that bleeds, upstream of the combustor, and pressurizes compressed air supplied from a compressor, that uses the bled and pressurized air to cool a wall, and that recovers and reuses the bled and pressurized air as combustion air for burning fuel in the combustor together with a main flow of the compressed air, wall cooling in which cooling air is supplied to cooling air passages formed in the wall of the combustor to perform cooling involves a downstream wall region, closer to a turbine, that is cooled using the bled and pressurized air as the cooling air and an upstream wall region, closer to a burner, that is cooled using, as the cooling air, bled compressed air bled from a main flow of the compressed air through a housing inner space.