This paper presents a multi-period location–production problem involving small recycling units that are embedded in standard containers and can, therefore, be relocated from site to site at short notice. The waste generated over time at different locations can be stored up to a specific limit, at which point recycling must occur. A mixed-integer program is implemented to plan the relocation of the mobile recycling units in such a way that the total cost resulting from waste transport and facility relocation is minimized. To solve large instances, three heuristics are developed that form the basis for a detailed computational study. The results reveal that mobile recycling units can significantly reduce the total costs compared to centralized recycling because (a) a larger number of mobile recycling units, (b) larger storage capacities, and (c) more short-term relocation possibilities increase the optimization scope and thus the possibility to reduce the total transport distances, and thereby, the costs. However, achieving this requires intelligent planning that considers the complex interdependencies between the influencing parameters and balances the existing trade-offs.