Cyphoderus innominatus Mills, 1938 (Collembola: Paronellidae) was first observed in early colonies of Atta sexdens leaf-cutting ants (Hymenoptera: Formicidae). The colonies were collected on February 6, 2019, from a transition area between the Atlantic Forest and the Cerrado, located in the municipality of Botucatu, São Paulo, Brazil. A total of four colonies collected had an average population density of 227 ± 212 C. innominatus individuals, and most of the latter were found in peripheral areas inside the fungus-garden-growing chamber of the colony. In addition, we observed a possible defensive behavior on the part of workers when C. innominatus individuals were present in the fungus garden chamber. Thus, this is the first record of C. innominatus living in association with early colonies of A. sexdens.