Solid-state recycling of used aluminum alloy beverage cans was accomplished by thermomechanical consolidation of the sheet fragments produced by shredding the cans. Different samples were obtained using two thermomechanical consolidation routes, one involving direct hot extrusion of a sheet fragment compact and the other involving upset hot-forging of a sheet fragment compact followed by hot extrusion of the forged ingot. The microstructures and mechanical properties of the samples were investigated. It was found that the samples contained less pores and exhibited better mechanical properties with a higher extrusion temperature and involving upset forging than with only hot extrusion, the highest tensile strength is 209.5 MPa and the largest elongation to fracture is 29.1%. The surface layers of the samples exhibited a clearly higher strength and tensile ductility than the interior. They also showed significantly different fracture behaviors, with the former being like fully ductile fracture and the latter involving delamination of the sheet fragments, suggesting that the bonding between the fragments is significantly stronger in the surface layer, possibly due to a higher amount of plastic deformation in it. Overall, the best quality solid state recycled material has tensile properties comparable with those of wrought aluminum alloy with the same composition.