Cyclodipeptide synthases (CDPSs) use two aminoacyl-tRNA substrates in a sequential ping-pong mechanism to form a cyclodipeptide. The crystal structures of three CDPSs have been determined and all show a Rossmann-fold domain similar to the catalytic domain of class-I aminoacyl-tRNA synthetases (aaRSs). Structural features and mutational analyses however suggest that CDPSs and aaRSs interact differently with their tRNA substrates. We used AlbC from Streptomyces noursei that mainly produces cyclo(l-Phe-l-Leu) to investigate the interaction of a CDPS with its substrates. We demonstrate that Phe-tRNA Phe is the first substrate accommodated by AlbC. Its binding to AlbC is dependent on basic residues located in the helix ␣4 that form a basic patch at the surface of the protein. AlbC does not use all of the Leu-tRNA Leu isoacceptors as a second substrate. We show that the G 1-C 72 pair of the acceptor stem is essential for the recognition of the second substrate. Substitution of D163 located in the loop ␣6–␣7 or D205 located in the loop ␤6–␣8 affected Leu-tRNA Leu isoacceptors specificity, suggesting the involvement of these residues in the binding of the second substrate. This is the first demonstration that the two substrates of CDPSs are accommodated in different binding sites.