Police were called to the Biffa depot in Avonmouth at 11:00 BST on Friday after being alerted by staff to possible remains at one of the units.
Avon and Somerset Police have named the victim as Matthew Symonds, 34, of no fixed address in Swindon, and said his death was being treated as unexplained.
A post-mortem examination is due to be carried out later.
His next of kin have been informed, police said.
Det Ch Insp Gareth Bevan said officers were "following several lines of inquiry" to establish the circumstances surrounding the man's death.
"Police inquiries so far suggest the body was transported with commercial recycling waste collected in Swindon and therefore the focus of the investigation will be in that area going forward," he said.
"The investigation is at an early stage and we are keeping an open mind about the circumstances leading to this man's death."
Police said it was too early to say how long the body parts had been there.
Biffa is one of the country's leading waste management companies, disposing of rubbish from commercial, industrial and public sector organisations.
Matthew Humphreys, from the company, said: "I can confirm that a body was received at our Avonmouth Transfer Station during the morning of Friday 1st August.
"Biffa takes health and safety very seriously and is conducting its own internal investigation, into the circumstances surrounding the incident."
A man whose body parts were found at a Bristol recycling plant has been identified as a Swindon man by police.